#include "prison.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= l; --x)
typedef long long ll;
using namespace std;
vector<int> ord = {3, 3, 3, 3, 3, 22};
vector<int> val;
void make_val(int x)
{
val.clear();
LoopR (i,0,ord.size()) {
val.push_back(x%ord[i]);
x /= ord[i];
}
reverse(val.begin(), val.end());
}
int get_nxt(bool ask, int k, int x)
{
make_val(x);
int nxt = 0;
int tmp = k;
while (tmp > 0)
tmp -= ord[nxt++];
int k2 = 1;
Loop (i,0,nxt)
k2 += ord[i];
if (k == 0)
return k2 + val[nxt];
// TODO: generalize
if (k <= 15) {
if ((k-1)%3 < val[nxt-1])
return ask? -1: -2;
if ((k-1)%3 > val[nxt-1])
return ask? -2: -1;
if (k2 == 16) {
if (val.back() == 0)
return ask? -2: -1;
if (val.back() == 21)
return ask? -1: -2;
if (val.back() <= 10)
return 16;
else
return 17;
}
return k2 + val[nxt];
}
if (k == 16) {
if (val.back() <= 1)
return ask? -2: -1;
if (val.back() >= 10)
return ask? -1: -2;
if (val.back() <= 5)
return 18;
else
return 19;
}
if (k == 17) {
if (val.back() <= 11)
return ask? -2: -1;
if (val.back() >= 20)
return ask? -1: -2;
if (val.back() <= 15)
return 18;
else
return 19;
}
if (k == 18) {
int x = val.back();
if (x > 10)
x -= 10;
if (x <= 2)
return ask? -2: -1;
if (x >= 5)
return ask? -1: -2;
return 20;
}
if (k == 19) {
int x = val.back();
if (x > 10)
x -= 10;
if (x <= 6)
return ask? -2: -1;
if (x >= 9)
return ask? -1: -2;
return 20;
}
if (k == 20) {
int x = val.back();
if (x > 10)
x -= 10;
if (x > 5)
x -= 4;
if (x <= 3)
return ask? -2: -1;
if (x >= 4)
return ask? -1: -2;
}
assert(!"aaa");
}
int who_to_ask(int k)
{
// TODO: generalize
int ans[] = {0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0};
return ans[k];
}
std::vector<std::vector<int>> devise_strategy(int N) {
vector<vector<int>> ans;
Loop (i,0,21) {
vector<int> vec(N+1);
vec[0] = who_to_ask(i);
Loop (j,0,N)
vec[j+1] = get_nxt(vec[0], i, j);
ans.push_back(vec);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
596 KB |
Output is correct |
5 |
Correct |
12 ms |
872 KB |
Output is correct |
6 |
Correct |
14 ms |
972 KB |
Output is correct |
7 |
Correct |
14 ms |
1000 KB |
Output is correct |
8 |
Correct |
1 ms |
296 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
6 ms |
596 KB |
Output is correct |
12 |
Correct |
11 ms |
852 KB |
Output is correct |