# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
48966 | Benq | Treasure (different grader from official contest) (CEOI13_treasure2) | C++14 | 0 ms | 0 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"
int cum[101][101], N;
/*int ans = 0, tmp[101][101];
void Report(int a, int b) {
assert(tmp[a][b] == 1);
// cout << a << " " << b << " " << tmp[a][b] << "\n";
}
int countTreasure(int a1, int b1, int a2, int b2) {
assert (a1 <= a2 && b1 <= b2);
int z = 0;
FOR(i,a1,a2+1) FOR(j,b1,b2+1) z += tmp[i][j];
ans += 50*50+1-(a2-a1+1)*(b2-b1+1);
return z;
}*/
int query(int a, int b) {
return cum[a][b]-cum[a-1][b]-cum[a][b-1]+cum[a-1][b-1];
}
void smart(int x, int y) {
if (x > N-x) {
if (y > N-y) {
cum[x][y] = countTreasure(1,1,x,y);
} else {
cum[x][y] = cum[x][N]-countTreasure(1,y+1,x,N);
}
} else {
if (y > N-y) {
cum[x][y] = cum[N][y]-countTreasure(x+1,1,N,y);
} else {
cum[x][y] = cum[x][N]+cum[N][y]-cum[N][N]+countTreasure(x+1,y+1,N,N);
}
}
}
void findTreasure (int n) {
N = n;
cum[N][N] = countTreasure(1,1,N,N);
FOR(i,1,N) {
if (i > N-i) {
cum[i][N] = countTreasure(1,1,i,N);
cum[N][i] = countTreasure(1,1,N,i);
} else {
cum[i][N] = cum[N][N]-countTreasure(i+1,1,N,N);
cum[N][i] = cum[N][N]-countTreasure(1,i+1,N,N);
}
}
FOR(i,1,N) FOR(j,1,N) smart(i,j);
FOR(i,1,N+1) FOR(j,1,N+1) if (query(i,j)) Report(i,j);
}