# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
4538 | kriii | Treasure (different grader from official contest) (CEOI13_treasure2) | C++98 | 3 ms | 2052 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "treasure.h"
#include <map>
using namespace std;
map<pair<int, int>, int> mem;
int T[111][111],R[111][111],D[111][111];
void add(int x1, int y1, int x2, int y2, int c)
{
int z1 = D[x1][x2], z2 = D[y1][y2];
mem[make_pair(z1,z2)] = c;
}
int get(int x1, int y1, int x2, int y2)
{
int z1 = D[x1][x2], z2 = D[y1][y2];
if (!mem.count(make_pair(z1,z2))) mem[make_pair(z1,z2)] = countTreasure(x1,y1,x2,y2);
return mem[make_pair(z1,z2)];
}
void findTreasure (int N)
{
int i,j,h,c=0;
for (i=1;i<=N;i++) for (j=1;j<=N;j++) R[i][j] = 0;
for (i=1;i<=N;i++) for (j=i;j<=N;j++) D[i][j] = ++c;
h = (N + 1) / 2;
mem.clear();
if (N % 2){
for (i=1;i<=h;i++) for (j=1;j<=h;j++) T[i][j] = get(i,j,N,N);
for (i=1;i<h;i++) for (j=1;j<h;j++) R[i][j] = T[i][j] - T[i+1][j] - T[i][j+1] + T[i+1][j+1];
c = 0;
for (i=1;i<h;i++) for (j=1;j<h;j++) c += R[i][j];
add(1,1,h-1,h-1,c);
for (i=h;i<=N;i++) for (j=h;j<=N;j++) T[i][j] = get(1,1,i,j);
for (i=h+1;i<=N;i++) for (j=h+1;j<=N;j++) R[i][j] = T[i][j] - T[i-1][j] - T[i][j-1] + T[i-1][j-1];
for (i=1;i<=h;i++) for (j=h;j<=N;j++) T[i][j] = get(i,1,N,j);
for (i=1;i<h;i++) for (j=h+1;j<=N;j++) R[i][j] = T[i][j] - T[i+1][j] - T[i][j-1] + T[i+1][j-1];
for (i=h;i<=N;i++) for (j=1;j<=h;j++) T[i][j] = get(1,j,i,N);
for (i=h+1;i<=N;i++) for (j=1;j<h;j++) R[i][j] = T[i][j] - T[i-1][j] - T[i][j+1] + T[i-1][j+1];
for (j=1;j<h;j++){
c = get(1,j,N,N)-get(1,j+1,N,N);
for (i=1;i<=N;i++) c -= R[i][j];
R[h][j] = c;
}
for (j=h+1;j<=N;j++){
c = get(1,1,N,j)-get(1,1,N,j-1);
for (i=1;i<=N;i++) c -= R[i][j];
R[h][j] = c;
}
for (i=1;i<h;i++){
c = get(i,1,N,N) - get(i+1,1,N,N);
for (j=1;j<=N;j++) c -= R[i][j];
R[i][h] = c;
}
for (i=h+1;i<=N;i++){
c = get(1,1,i,N) - get(1,1,i-1,N);
for (j=1;j<=N;j++) c -= R[i][j];
R[i][h] = c;
}
c = get(1,1,N,N);
for (i=1;i<=N;i++) for (j=1;j<=N;j++) c -= R[i][j];
R[h][h] = c;
}
else{
for (i=1;i<=h+1;i++) for (j=1;j<=h+1;j++) T[i][j] = get(i,j,N,N);
for (i=1;i<=h;i++) for (j=1;j<=h;j++) R[i][j] = T[i][j] - T[i+1][j] - T[i][j+1] + T[i+1][j+1];
for (i=2;i<=h+1;i++) add(1,1,i-1,N,T[1][1]-T[i][1]);
for (j=2;j<=h+1;j++) add(1,1,N,j-1,T[1][1]-T[1][j]);
c = 0;
for (i=1;i<=h;i++) for (j=1;j<=h;j++) c += R[i][j];
add(1,1,h,h,c);
for (i=h;i<=N;i++) for (j=h;j<=N;j++) T[i][j] = get(1,1,i,j);
for (i=h+1;i<=N;i++) for (j=h+1;j<=N;j++) R[i][j] = T[i][j] - T[i-1][j] - T[i][j-1] + T[i-1][j-1];
for (i=1;i<=h;i++) for (j=h+1;j<=N;j++) T[i][j] = get(i,1,N,j);
for (i=1;i<h;i++) for (j=h+2;j<=N;j++) R[i][j] = T[i][j] - T[i+1][j] - T[i][j-1] + T[i+1][j-1];
for (i=h+1;i<=N;i++) for (j=1;j<=h;j++) T[i][j] = get(1,j,i,N);
for (i=h+2;i<=N;i++) for (j=1;j<h;j++) R[i][j] = T[i][j] - T[i-1][j] - T[i][j+1] + T[i-1][j+1];
for (j=1;j<h;j++){
c = get(1,j,N,N)-get(1,j+1,N,N);
for (i=1;i<=N;i++) c -= R[i][j];
R[h+1][j] = c;
}
for (j=h+2;j<=N;j++){
c = get(1,1,N,j)-get(1,1,N,j-1);
for (i=1;i<=N;i++) c -= R[i][j];
R[h][j] = c;
}
for (i=1;i<h;i++){
c = get(i,1,N,N) - get(i+1,1,N,N);
for (j=1;j<=N;j++) c -= R[i][j];
R[i][h+1] = c;
}
for (i=h+2;i<=N;i++){
c = get(1,1,i,N) - get(1,1,i-1,N);
for (j=1;j<=N;j++) c -= R[i][j];
R[i][h] = c;
}
c = get(1,1,N,h);
for (i=1;i<=N;i++) for (j=1;j<=h;j++) c -= R[i][j];
R[h+1][h] = c;
c = get(1,h+1,N,N);
for (i=1;i<=N;i++) for (j=h+1;j<=N;j++) c -= R[i][j];
R[h][h+1] = c;
}
for (i=1;i<=N;i++) for (j=1;j<=N;j++) if(R[i][j] == 1) Report(i, j);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |