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"
#include "prison.h"
using namespace std;
using ll = long long;
#define sz(v) ((int)v.size())
#define pb push_back
vector<array<int, 6>> nd;
int dfs(int x) {
int s = nd[x][1] - nd[x][0] + 1;
nd[x][5] = 0;
if (s <= 2) return 0;
s -= 2;
int e = s / 3;
int e1, e2, e3;
if (!e) {
nd[x][2] = sz(nd);
nd.pb({nd[x][0]+1, nd[x][1] - 1, 0, 0, 0});
nd[x][5] = 1;
return 1;
}
if (s < 5) {
nd[x][2] = sz(nd);
nd[x][3] = sz(nd)+1;
nd[x][5] = 2;
nd.pb({nd[x][0]+1, nd[x][0]+2, 0, 0, 0, 0});
nd.pb({nd[x][0]+3, nd[x][1]-1, 0, 0, 0, 0});
return 2;
}
e1 = e2 = e3 = e;
if (s % 3) ++e1;
if (s % 3 == 2) ++e2;
nd[x][2] = sz(nd);
nd[x][3] = sz(nd)+1;
nd[x][4] = sz(nd)+2;
int v1, v2, v3;
nd.pb({nd[x][0]+1, nd[x][0]+e1, 0, 0, 0});
nd.pb({nd[x][0]+1+e1, nd[x][0]+e1+e2, 0, 0, 0});
nd.pb({nd[x][0]+1+e1+e2, nd[x][0]+e1+e3, 0, 0, 0});
v1 = dfs(nd[x][2]);
v2 = dfs(nd[x][3]);
v3 = dfs(nd[x][4]);
nd[x][5] = 3;
return 3 + max({v1, v2, v3});
}
int dfs1(int x, int v, int d) {
if (d <= nd[x][5]) return x;
d -= nd[x][5];
assert(v != nd[x][0]);
assert(v != nd[x][1]);
if (nd[nd[x][2]][1] >= v) return dfs1(nd[x][2], v, d);
if (nd[nd[x][3]][1] >= v) return dfs1(nd[x][3], v, d);
if (nd[nd[x][4]][1] >= v) return dfs1(nd[x][4], v, d);
assert(0);
}
int s[] = {1700, 566, 188, 62, 20, 6, 2};
int query(int x, int y) {
/* Get if it's either A or B */
int u = 0; int z = x;
int l = 1, cb = 0;
while (z) {
u = 1-u;
if (z < 4)
break;
z -= 3;
}
if (y == 0) {
return u;
}
z = x;
if (z == 0) {
if (y == 1)
return -1;
if (y < 1 + s[cb])
return 1;
if (y < 1 + 2*s[cb])
return 2;
return 3;
}
while (z) {
if (y == l)
return - 1 - u;
if (y == l + 1 + 3 * s[cb])
return u - 2;
if (cb == 5 && y == l + 1 + 3 * s[cb])
return u - 2;
if (z < 4)
break;
z -= 3;
++l;
while (y >= l + s[cb])
l += s[cb];
++cb;
}
if (y < l + 1 + (z-1) * s[cb])
return -1-u;
if (y >= l + 1 + z * s[cb])
return u-2;
++l;
while (y >= l + s[cb])
l += s[cb];
++cb;
if (cb == 7)
if (y == l)
return -1-u;
else
return u-2;
if (cb == 6) {
if (y == l)
return -1-u;
else if (y == l + 5)
return u-2;
if (y < l + 3) return 19;
else return 20;
}
if (y == l)
return - 1 - u;
if (y == l + 1 + 3 * s[cb])
return u - 2;
if (y < l + s[cb] + 1) return cb*3 + 1;
if (y < l + 2*s[cb] + 1) return cb*3 + 2;
return cb * 3 + 3;
}
vector<vector<int>> devise_strategy(int n) {
int x = 20;
// nd.pb({1, 5102, 0, 0, 0});
// dfs(0);
vector<vector<int>> ans(x+1);
for (int i = 0; i <= x; ++i) {
ans[i].assign(n+1, 0);
for (int j = 0; j <= n; ++j) {
ans[i][j] = query(i, j);
}
}
return ans;
}
#ifdef ONPC
int main()
{
int n;
cin >> n;
vector<vector<int>> a = devise_strategy(n);
for (auto x : a) {
for (auto u : x) {
cout << u << ' ';
}
cout << endl;
}
}
#endif
Compilation message (stderr)
prison.cpp: In function 'int query(int, int)':
prison.cpp:132:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
132 | if (cb == 7)
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |