| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 249548 | Kevin_Zhang_TW | Treasure (different grader from official contest) (CEOI13_treasure2) | C++17 | 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<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
const int maxn = 110;
int n;
bool res[maxn][maxn];
vector<string> tst;
void init() {
cin >> n;
tst.resize(n);
for (int i = 0;i < n;++i) {
for (int j = 0;j < n;++j)
tst[i].push_back(((rand()&(1<<10))>>10)+'0');
cout << tst[i] << '\n';
}
}
int BCNT(pair<int,int> LD, pair<int,int> UR) {
int res = 0;
for (int i = LD.first-1;i < UR.first;++i)
for (int j = LD.second-1;j < UR.second;++j)
res += tst[i][j] == '1';
return res;
}
int query(pair<int,int> LD, pair<int,int> UR) {
if (min(UR.first, UR.second) < 1) return 0;
if (max(LD.first, LD.second) > n) return 0;
static int res;
cout << LD.first << ' ' << LD.second << ' ' << UR.first << ' ' << UR.second << endl;
//#ifdef KEV
//// cout << "IS " << BCNT(LD, UR) << '\n';
// return BCNT(LD, UR);
//#endif
cin >> res;
return res;
}
void reply() {
cout << "END\n";
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= n;++j)
cout << char(res[i][j] + '0');
cout << '\n';
}
}
int cur_row;
int mcnt(pair<int,int> LD, pair<int,int> UR) {
int res = 0;
for (int i = LD.first;i <= UR.first;++i)
for (int j = LD.second;j <= UR.second;++j)
res += ::res[i][j];
return res;
}
void solve2(int l, int r, int all) {
if (!all) return;
if (r-l+1 == all) {
fill(res[cur_row]+l, res[cur_row]+r+1, true);
return;
}
int m = l + r >> 1;
int lall = query({1, 1}, {cur_row, m})
- mcnt({1, 1}, {cur_row-1, m})
- mcnt({1, 1}, {cur_row, l-1})
+ mcnt({1, 1}, {cur_row-1, l-1})
, rall = all - lall;
//int llall = query({cur_row, l}, {cur_row, m}), rrall = all - lall;
//cerr << "LALL LLALL " << lall << ' ' << llall << '\n';
solve2(l, m, lall), solve2(m+1, r, rall);
}
void solve1(int l, int r, int all) {
if (!all) return;
if (n * (r-l+1) == all) {
for (int i = l;i <= r;++i)
fill(res[i]+1, res[i]+1+n, true);
return;
}
if (l == r) {
cur_row = l;
solve2(1, n, all);
return;
}
int m = l + r >> 1;
int lall = query({l, 1}, {m, n}), rall = all - lall;
solve1(l, m, lall), solve1(m+1, r, rall);
}
int pf[maxn][maxn];
void good() {
int all = query({1,1}, {n,n});
//if (n > 20) return;
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= n;++j) {
int a, b, c, d;
//a = mcnt({1, 1}, {i-1, n}) ,
a = pf[i-1][n];
b = (i > n-i ? all - query({1, 1}, {i, n}) : query({i+1, 1}, {n, n})) ;//,
c = (j > n-j ? query({1, 1}, {n, j-1}) : all - query({1, j}, {n, n})) ;
d = (j > n-j ? all - query({1, 1}, {n, j}) : query({1, j+1}, {n, n}));
//int a = query({1, 1}, {i-1, n}),
//b = query({i+1,1}, {n, n}),
//c = query({1, 1}, {n, j-1}),
//d = query({1, j+1}, {n, n});
res[i][j] = all
- a - b - c - d
//+ mcnt({1,1}, {i-1,j-1})
//+ mcnt({1,j+1}, {i-1, n})
+ query({1, 1}, {i-1, j-1})
+ query({1, j+1}, {i-1, n})
+ query({i+1,1}, {n,j-1})
+ query({i+1,j+1}, {n, n})
;
pf[i][j] = pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1] + res[i][j];
//cout << i << ' ' << j << " : " << res[i][j] << '\n';
}
}
}
//void boo(pair<int,int> LD, pair<int,int> UR, int sum) {
// if (!sum) return;
// if (sum == (UR.first-LD.first+1) * (UR.second-LD.second+1)) {
// for (int i = LD.first;i <= UR.first;++i)
// fill(res[i]+LD.second, res[i]+UR.second+1, true);
// return;
// }
// int mr = LD.first + UR.first >> 1, mc = LD.second + UR.second >> 1;
// int a = query({1,1}, {mr, UR.second})
// - mcnt({1, 1}, {mr, UR.second}),
// b = query({1,1}, {UR.first, mc})
// - mcnt({1, 1}, {UR.first, mc});
// int s =
//
//+ mcnt({LD.first, LD.second}, {
signed main(){
ios_base::sync_with_stdio(0), cin.tie(0);
//#ifdef KEV
// init();
//#endif
cin >> n;
good();
reply();
return 0;
//int all = query({1,1}, {n,n});
//solve1(1, n, all);
//boo({1,1}, {n,n}, all);
//reply();
}