#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
const int MAX_N = 300;
int n;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
vector<int> p{1,2,3,4,5,6,7,8,9,10,11,12,13};
int qcnt;
int query(vector<int> q) {
++qcnt;
int res = 0;
for (int i = 0;i < n;++i)
res += p[i] == q[i];
if (res == n)
DE(n, qcnt);
return res;
}
#else
#define DE(...) 0
void debug(...) {}
#include "grader.h"
#endif
random_device rd;
mt19937 gen(rd());
//int query(int q[]) {
// return query(vector<int>(q, q+n));
//}
vector<int> pos(n);
vector<int> val(n);
vector<int> q(n);
int cur_same;
int dfs(int x, vector<int> pos) {
if (pos.size() == 1)
return ++cur_same, pos[0];
int n = pos.size()-1, m = n / 2;
//DE(x);
//debug(AI(pos));
vector<int> L, R;
for (int i = 0;i <= n;++i)
(i<=m?L:R).pb( pos[i] );
//DE(L.size(), R.size(), pos.size());
for (int u : L)
q[u] = x;
int v = query(q);
if (v > cur_same) {
for (int u : L)
q[u] = 0;
return dfs(x, L);
}
else
return dfs(x, R);
}
void solve(int N) {
n = N;
cur_same = 0;
val = q = pos = vector<int>(n);
iota(AI(pos), 0);
iota(AI(val), 1);
shuffle(AI(val), gen);
shuffle(AI(pos), gen);
while (pos.size()) {
if (pos.size() == 1) {
int x = pos[0];
q[x] = val[0];
break;
}
else {
int x = val.back(); val.pop_back();
//int y = val.back(); val.pop_back();
int p = dfs(x, pos);
q[p] = x;
pos.erase(find(AI(pos), p));
}
}
query(q);
}
#ifdef KEV
int main() {
solve(p.size());
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
256 KB |
Integer 0 violates the range [1, 7] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
256 KB |
Integer 0 violates the range [1, 7] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
256 KB |
Integer 0 violates the range [1, 7] |
2 |
Halted |
0 ms |
0 KB |
- |