#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include "treasure.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end()
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int mxN = 105;
template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }
int n, tot;
int l[mxN], r[mxN], u[mxN], d[mxN]; //all of these are inclusive
int LU[mxN][mxN], LD[mxN][mxN], RU[mxN][mxN], RD[mxN][mxN];
int qry(int r1, int c1, int r2, int c2){
int ret = countTreasure(r1, c1, r2, c2);
return ret;
}
bool check(int i, int j){
int cur = 0;
if(i > 1) cur += u[i - 1];
if(i < n) cur += d[i + 1];
if(j > 1) cur += l[j - 1];
if(j < n) cur += r[j + 1];
//now we do the intersections
if(i > 1 && j > 1) cur -= LU[i - 1][j - 1];
if(i < n && j > 1) cur -= LD[i + 1][j - 1];
if(i > 1 && j < n) cur -= RU[i - 1][j + 1];
if(i < n && j < n) cur -= RD[i + 1][j + 1];
//assert(cur == tot || cur == (tot - 1));
return cur != tot;
}
void solve(int i, int j){
if(k == 1){
if(~RU[i][j]) return;
int q = qry(1, j, i, n);
RU[i][j] = q;
if(j > 1) LU[i][j - 1] = u[i] - RU[i][j];
if(i < n){
RD[i + 1][j] = r[j] - RU[i][j];
if(j > 1) LD[i + 1][j - 1] = l[j - 1] - LU[i][j - 1];
}
}
if(k == 2){
if(~LU[i][j]) return;
int q = qry(1, 1, i, j);
LU[i][j] = q;
if(i < n) LD[i + 1][j] = l[j] - LU[i][j];
if(j < n){
RU[i][j + 1] = u[i] - LU[i][j];
if(i < n) RD[i + 1][j + 1] = r[j + 1] - RU[i][j + 1];
}
}
if(k == 3){
if(~RD[i][j]) return;
int q = qry(i, j, n, n);
RD[i][j] = q;
if(i > 1) RU[i - 1][j] = r[j] - RD[i][j];
if(j > 1){
LD[i][j - 1] = d[i] - RD[i][j];
if(i > 1) LU[i - 1][j - 1] = l[j - 1] - LD[i][j - 1];
}
}
if(k == 4){
if(~LD[i][j]) return;
int q = qry(i, 1, n, j);
LD[i][j] = q;
if(i > 1) LU[i - 1][j] = l[j] - LD[i][j];
if(j < n){
RD[i][j + 1] = d[i] - LD[i][j];
if(i > 1) RU[i - 1][j + 1] = r[j + 1] - RD[i][j + 1];
}
}
}
void findTreasure(int N){
n = N;
memset(LD, -1, sizeof(LD));
memset(LU, -1, sizeof(LU));
memset(RD, -1, sizeof(RD));
memset(RU, -1, sizeof(RU));
tot = qry(1, 1, n, n);
//l and r
l[n] = r[1] = tot;
repn(i, 1, n){
if(i > (n - i)) l[i] = qry(1, 1, n, i);
else l[i] = tot - qry(1, i + 1, n, n);
}
repn(i, 2, n + 1) r[i] = tot - l[i - 1];
//u and d
u[n] = d[1] = tot;
repn(i, 1, n){
if(i > (n - i)) u[i] = qry(1, 1, i, n);
else u[i] = tot - qry(i + 1, 1, n, n);
}
repn(i, 2, n + 1) d[i] = tot - u[i - 1];
//corners
repn(i, 1, n + 1){
repn(j, 1, n + 1){
if(i < (n - i)){
if(j < (n - j)) solve(i, j, 3);
else solve(i, j, 4);
}
else{
if(j < (n - j)) solve(i, j, 1);
else solve(i, j, 2);
}
}
}
repn(i, 1, n + 1){
repn(j, 1, n + 1){
if(RU[i][j] == -1) solve(i, j, 1);
if(LU[i][j] == -1) solve(i, j, 2);
if(RD[i][j] == -1) solve(i, j, 3);
if(LD[i][j] == -1) solve(i, j, 4);
}
}
repn(i, 1, n + 1){
repn(j, 1, n + 1){
if(check(i, j)) Report(i, j);
}
}
}
/*
Things to look out for:
- Integer overflows
- Array bounds
- Special cases
Be careful!
*/
Compilation message
treasure.cpp: In function 'void solve(int, int)':
treasure.cpp:51:5: error: 'k' was not declared in this scope
51 | if(k == 1){
| ^
treasure.cpp:61:5: error: 'k' was not declared in this scope
61 | if(k == 2){
| ^
treasure.cpp:71:5: error: 'k' was not declared in this scope
71 | if(k == 3){
| ^
treasure.cpp:81:5: error: 'k' was not declared in this scope
81 | if(k == 4){
| ^
treasure.cpp: In function 'void findTreasure(int)':
treasure.cpp:118:34: error: too many arguments to function 'void solve(int, int)'
118 | if(j < (n - j)) solve(i, j, 3);
| ^
treasure.cpp:50:6: note: declared here
50 | void solve(int i, int j){
| ^~~~~
treasure.cpp:119:23: error: too many arguments to function 'void solve(int, int)'
119 | else solve(i, j, 4);
| ^
treasure.cpp:50:6: note: declared here
50 | void solve(int i, int j){
| ^~~~~
treasure.cpp:122:34: error: too many arguments to function 'void solve(int, int)'
122 | if(j < (n - j)) solve(i, j, 1);
| ^
treasure.cpp:50:6: note: declared here
50 | void solve(int i, int j){
| ^~~~~
treasure.cpp:123:23: error: too many arguments to function 'void solve(int, int)'
123 | else solve(i, j, 2);
| ^
treasure.cpp:50:6: note: declared here
50 | void solve(int i, int j){
| ^~~~~
treasure.cpp:129:36: error: too many arguments to function 'void solve(int, int)'
129 | if(RU[i][j] == -1) solve(i, j, 1);
| ^
treasure.cpp:50:6: note: declared here
50 | void solve(int i, int j){
| ^~~~~
treasure.cpp:130:36: error: too many arguments to function 'void solve(int, int)'
130 | if(LU[i][j] == -1) solve(i, j, 2);
| ^
treasure.cpp:50:6: note: declared here
50 | void solve(int i, int j){
| ^~~~~
treasure.cpp:131:36: error: too many arguments to function 'void solve(int, int)'
131 | if(RD[i][j] == -1) solve(i, j, 3);
| ^
treasure.cpp:50:6: note: declared here
50 | void solve(int i, int j){
| ^~~~~
treasure.cpp:132:36: error: too many arguments to function 'void solve(int, int)'
132 | if(LD[i][j] == -1) solve(i, j, 4);
| ^
treasure.cpp:50:6: note: declared here
50 | void solve(int i, int j){
| ^~~~~
