| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1294177 | Math4Life2020 | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
vector<int> construct_range(int M, int K) {
// ll N = M;
// vector<int> vf;
// vf.push_back(1);
// for (ll i=1;i<N;i++) {
// vf.push_back(i);
// }
// return vf;
vector<int> vf(M,M-1);
vector<ll> v0;
ll tsum = 0;
ll cv = 1;
while (tsum<(4*M)) {
v0.push_back(cv);
tsum += cv;
cv += 2;
}
for (ll x: v0) {
for (ll y: v0) {
ll xf = (x+y)/2;
ll yf = (y-x)/2;
if (yf>0 && xf<M) {
vf[xf]=min(vf[xf],yf);
}
}
}
return vf;
}
long long count_triples(vector<int> H) {
ll N = H.size();
ll ans = 0;
//H[x]=z-x H[y]=z-y H[z]=y-x
// for (ll x=0;x<N;x++) {
// for (ll y=(x+1);y<N;y++) {
// for (ll z=(y+1);z<N;z++) {
// if (H[x]==(z-x) && H[y]==(z-y) && H[z]==(y-x)) {
// ans++;
// }
// }
// }
// }
for (ll x=0;x<N;x++) {
ll z = x+H[x];
if (z<N) {
ll y=H[z]+x;
if (y<N) {
if ((H[y]+y)==z && x<y && y<z && (z-y)!=(y-x)) {
ans++;
}
}
}
}
//H[x]=z-x H[y]=y-x H[z]=z-y
// for (ll x=0;x<N;x++) {
// for (ll y=(x+1);y<N;y++) {
// for (ll z=(y+1);z<N;z++) {
// if (H[x]==(z-x) && H[y]==(y-x) && H[z]==(z-y)) {
// ans++;
// }
// }
// }
// }
for (ll x=0;x<N;x++) {
ll z = x+H[x];
if (z<N) {
ll y = z-H[z];
if (y>=0) {
if (H[y]==(y-x) && x<y && y<z) {
ans++;
}
}
}
}
//H[x]=y-x, H[y]=z-x, H[z]=z-y
// for (ll x=0;x<N;x++) {
// for (ll y=(x+1);y<N;y++) {
// for (ll z=(y+1);z<N;z++) {
// if (H[x]==(y-x) && H[y]==(z-x) && H[z]==(z-y)) {
// ans++;
// }
// }
// }
// }
for (ll x=0;x<N;x++) {
ll y=x+H[x];
if (y<N) {
ll z = x+H[y];
if (z<N) {
if (H[z]==(z-y) && x<y && y<z && (z-y)!=(y-x)) {
ans++;
}
}
}
}
//H[x]=y-x, H[y]=z-y, H[z]=z-x
// for (ll x=0;x<N;x++) {
// for (ll y=(x+1);y<N;y++) {
// for (ll z=(y+1);z<N;z++) {
// if (H[x]==(y-x) && H[y]==(z-y) && H[z]==(z-x)) {
// ans++;
// }
// }
// }
// }
for (ll x=0;x<N;x++) {
ll y=x+H[x];
if (y<N) {
ll z = y+H[y];
if (z<N) {
if (H[z]==(z-x) && x<y && y<z && (z-y)!=(y-x)) {
ans++;
}
}
}
}
//H[x]=z-y, H[y]=y-x, H[z]=z-x
// for (ll x=0;x<N;x++) {
// for (ll y=(x+1);y<N;y++) {
// for (ll z=(y+1);z<N;z++) {
// if (H[x]==(z-y) && H[y]==(y-x) && H[z]==(z-x)) {
// ans++;
// }
// }
// }
// }
for (ll y=0;y<N;y++) {
ll x = y-H[y];
if (x>=0) {
ll z = y+H[x];
if (z<N) {
if (H[z]==(z-x) && x<y && y<z) {
ans++;
}
}
}
}
//H[x]=z-y, H[y]=z-x, H[z]=y-x
// for (ll x=0;x<N;x++) {
// for (ll y=(x+1);y<N;y++) {
// for (ll z=(y+1);z<N;z++) {
// if (H[x]==(z-y) && H[y]==(z-x) && H[z]==(y-x)) {
// ans++;
// }
// }
// }
// }
vector<ll> va[N];
vector<ll> vb[N];
for (ll x=0;x<N;x++) {
if ((x+H[x])<N) {
va[x+H[x]].push_back(x);
}
if ((x-H[x])>=0) {
vb[x-H[x]].push_back(x);
}
}
for (ll r=0;r<N;r++) {
ll A = va[r].size(); ll B=vb[r].size();
if ((A*B)>=N) {
for (ll x0=0;x0<N;x0++) {
ll y0 = H[x0];
if ((x0+y0)%2==(r%2)) {
ll x1 = (x0+y0+r)/2;
ll y1 = (x0+y0-r)/2;
ll x2 = (r+x0-y0)/2;
ll y2 = (y0-x0+r)/2;
if (x1<N && x1>=0 && x2<N && x2>=0) {
if (H[x1]==y1 && H[x2]==y2) {
ans++;
}
}
}
}
} else {
//manual: A*B
for (ll xa: va[r]) {
ll ya = H[xa];
for (ll xb: vb[r]) {
ll yb = H[xb];
ll xf = xa+xb-r;
ll yf = ya+yb;
if (xf>=0 && xf<N) {
if (H[xf]==yf) {
ans++;
}
}
}
}
}
}
return ans;
}