#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
map<vector<int>, int> mp;
int que(vector<int> v){
if(mp.count(v)) return mp[v];
return mp[v] = query(v);
}
mt19937 rng(694201273);
void solve(int N) {
if(N <= 4){
vector<int> v;
for(int i = 1; i <= N; i ++)
v.push_back(i);
do{
int get = que(v);
if(get == N) return;
}while(next_permutation(v.begin(), v.end()));
return;
}
vector<int> perm(N);
iota(perm.begin(), perm.end(), 1);
for(;;){
shuffle(perm.begin(), perm.end(), rng);
int get = que(perm);
if(get == N) return;
if(get == 0) break;
}
// cout << "DONE RANDOM" << endl;
vector<int> get_count(N + 1, 0);
for(int i = 1; i <= N; i ++){
vector<int> v(N);
for(int id, j = 0; j < N; j ++){
id = j + i;
if(id > N) id -= N;
v[j] = perm[id - 1];
}
get_count[i] = que(v);
if(get_count[i] == N) return;
}
int start_from = 1;
for(int i = 1; i <= N; i ++)
if(get_count[i] == 0){
start_from = i;
break;
}
vector<int> order_of_visit;
for(int i = start_from, cnt = 0; cnt < N; cnt ++){
order_of_visit.push_back(i);
i ++; if(i > N) i -= N;
}
int front_element = 0;
{
vector<int> asking;
for(int j = 0; j < N; j ++){
asking.push_back(j + start_from);
if(asking.back() > N) asking.back() -= N;
asking.back() = perm[asking.back() - 1];
}
vector<int> id_change;
int unid_change = 0;
for(int j = 1; j < N; j ++){
// cout << "OWO" << endl;
swap(asking[0], asking[j]);
int get = que(asking);
if(get == N) return;
if(get != 0) id_change.push_back(j);
else unid_change = j;
swap(asking[0], asking[j]);
if(id_change.size() == 2) break;
if(get == 2) break;
}
if(id_change.size() == 1){
front_element = asking[id_change[0]];
}else{
assert(id_change.size() == 2);
swap(asking[0], asking[id_change[0]]);
swap(asking[0], asking[id_change[1]]);
int get = que(asking);
if(get == N) return;
swap(asking[0], asking[id_change[1]]);
swap(asking[0], asking[id_change[0]]);
if(get == 2) front_element = asking[id_change[1]];
else front_element = asking[id_change[0]];
}
}
assert(front_element != 0);
// cout << front_element << endl;
int times_break_probably_because_its_first_element = 0;
vector<vector<int> > good_positions(N + 1, vector<int>());
for(int owo = 1; owo < N; owo ++){
int offset = order_of_visit[owo];
// cout << "offset now = " << offset << endl;
int last_offset = offset - 1; if(last_offset < 1) last_offset += N;
int lf = 0, rg = N - 1, bts = 1;
for(int times = 0; times < get_count[offset]; times ++){
int valid_pos = -1;
for(int md; lf <= rg;){
md = (lf + rg) / 2;
vector<int> asking;
for(int j = 0; j < N; j ++){
asking.push_back(j + offset);
if(asking.back() > N) asking.back() -= N;
asking.back() = perm[asking.back() - 1];
}
// rotate [0, md]
int tmp = asking[md];
for(int j = md - 1; j >= 0; j --)
asking[j + 1] = asking[j];
asking[0] = tmp;
int get = que(asking);
if(get == N) return;
int collide = 0;
for(int j : good_positions[last_offset]){
if(j == 0) continue;
if(j > md) break;
collide ++;
}
if(asking[0] == front_element) collide ++;
// cout << "get " << get << " collide " << collide << ", bts " << bts << " (lf, rg) " << lf << " " << rg << endl;
// cout << "asking ";
// for(int ngeh : asking) cout << ngeh << " ";
// cout << endl;
if(get - collide >= bts){
valid_pos = md;
lf = md + 1;
}else if(get - collide < bts){
rg = md - 1;
}
}
if(valid_pos == -1){
times_break_probably_because_its_first_element += get_count[offset] - times;
assert(times_break_probably_because_its_first_element <= 1);
break;
}
rg = valid_pos; lf = 0; bts ++;
good_positions[offset].push_back(valid_pos + 1);
}
reverse(good_positions[offset].begin(), good_positions[offset].end());
}
vector<int> ans(N, 0);
ans[0] = front_element;
for(int i = 1; i <= N; i ++){
vector<int> v(N, 0);
for(int j = 0; j < N; j ++){
v[j] = j + i;
if(v[j] > N) v[j] -= N;
v[j] = perm[v[j] - 1];
}
// cout << "good_positions " << i << ": ";
for(int j : good_positions[i]){
// cout << j << " ";
ans[j] = v[j];
}
// cout << endl;
}
int get = que(ans);
assert(get == N);
return;
}
Compilation message
mouse.cpp: In function 'void solve(int)':
mouse.cpp:68:7: warning: variable 'unid_change' set but not used [-Wunused-but-set-variable]
68 | int unid_change = 0;
| ^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 25 |
| 2 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 18 |
| 3 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 25 |
| 4 |
Runtime error |
2 ms |
456 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 25 |
| 2 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 18 |
| 3 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 25 |
| 4 |
Runtime error |
2 ms |
456 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 25 |
| 2 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 18 |
| 3 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 25 |
| 4 |
Runtime error |
2 ms |
456 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
