#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint,lint> ii;
int solved[260];
void solve(int n) {
srand(time(NULL));
vector<int> best;
for(int i = 1; i <= n; i++) best.push_back(i);
while(true){
random_shuffle(all(best));
best.pop_back();
if(query(best) == 0) break;
}
vector<int> unknown;
int cur = 0;
int known = -1;
while(true){
unknown.clear();
for(int i = 0; i < n; i++){
if(not solved[i]) unknown.push_back(i);
else known = i;
}
random_shuffle(all(unknown));
vector<int> test;
for(int x : best) test.push_back(x);
for(int i = 0;i+1 < sz(unknown);i += 2){
swap(test[unknown[i]], test[unknown[i+1]]);
}
int nxt = query(test);
if(nxt == n) return;
if(nxt == cur) continue;
if(nxt > cur){
//cout << "U: "; for(int x : unknown) cout << x << " "; cout << endl;
////cout << "P: "; for(int i = 0;i < n;i++) cout << i << " "; cout << endl;
//cout << "B: "; for(int x : best) cout << x << " "; cout << endl;
int low = -1; int high = sz(unknown)/2 - 1;
while(low != high-1){
int mid = (low+high)/2;
test.clear(); for(int x : best) test.push_back(x);
for(int i = 0;i <= mid;i++){
swap(test[unknown[i*2]], test[unknown[i*2+1]]);
}
int res = query(test);
if(res == n) return;
if(res > cur) high = mid;
else low = mid;
}
int a = unknown[high*2], b = unknown[high*2+1];
swap(best[a], best[b]);
int newcur = query(best);
if(newcur == n) return;
if(newcur - cur == 2){
solved[a] = 1;
solved[b] = 1;
}
else{
if(known == -1){
int x = 1;
while(x == a or x == b) x++;
vector<int> test; for(int x : best) test.push_back(x);
swap(test[x], test[a]);
if(query(test) < newcur) solved[a] = 1;
else solved[b] = 1;
}
else{
vector<int> test; for(int x : best) test.push_back(x);
swap(test[known], test[a]);
if(query(test) == newcur-1) solved[b] = 1;
else solved[a] = 1;
}
}
cur = newcur;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
