#include <bits/stdc++.h>
#include "xylophone.h"
const int maxn = 5e3 + 5;
bool check[maxn];
std::mt19937 rd(std::chrono::steady_clock::now().time_since_epoch().count());
int randint(int l, int r){
assert(l <= r);
return std::uniform_int_distribution<int>(l, r)(rd);
}
void solve(int N){
int l = 1;
int r = N;
while(l < r){
int mid = (l + r) >> 1;
int res = query(1, mid);
if(res != N - 1){
l = mid + 1;
}else{
r = mid;
}
}
int posr = l;
answer(posr, N);
check[N] = true;
l = 1, r = N;
while(l < r - 1){
int mid = (l + r) >> 1;
int res = query(mid, N);
if(res != N - 1){
r = mid - 1;
}else{
l = mid;
}
}
int posl = l;
if(query(r, N) == N - 1) posl = r;
answer(posl, 1);
int ptr1 = posl - 1, ptr2 = posl + 1, ptr3 = posr + 1;
int cur1 = 1, cur2 = 1, cur3 = N;
int cnt = 2;
while(cnt < N){
int type = randint(1, 3);
if(type == 1 && ptr1 >= 1){
int diff = query(ptr1, ptr1 + 1);
int waifu1 = cur1 + diff;
int waifu2 = cur1 - diff;
if(waifu2 <= 0 || check[waifu2]){
answer(ptr1, waifu1);
check[waifu1] = true;
cur1 = waifu1;
ptr1--;
cnt++;
}else if(waifu1 > N || check[waifu1]){
answer(ptr1, waifu2);
check[waifu2] = true;
cur1 = waifu2;
ptr1--;
cnt++;
}
}else if(type == 2 && ptr2 >= posl && ptr2 < posr){
int diff = query(ptr2 - 1, ptr2);
int waifu1 = cur2 + diff;
int waifu2 = cur2 - diff;
if(waifu2 <= 0 || check[waifu2]){
answer(ptr2, waifu1);
check[waifu1] = true;
cur2 = waifu1;
ptr2++;
cnt++;
}else if(waifu1 > N || check[waifu1]){
answer(ptr2, waifu2);
check[waifu2] = true;
cur2 = waifu2;
ptr2++;
cnt++;
}
}else if(type == 3 && ptr3 <= N){
int diff = query(ptr3 - 1, ptr3);
int waifu1 = cur3 + diff;
int waifu2 = cur3 - diff;
if(waifu2 <= 0 || check[waifu2]){
answer(ptr3, waifu1);
check[waifu1] = true;
cur3 = waifu1;
ptr3++;
cnt++;
}else if(waifu1 > N || check[waifu1]){
answer(ptr3, waifu2);
check[waifu2] = true;
cur3 = waifu2;
ptr3++;
cnt++;
}
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Incorrect |
62 ms |
208 KB |
Wrong Answer [2] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Incorrect |
62 ms |
208 KB |
Wrong Answer [2] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Incorrect |
62 ms |
208 KB |
Wrong Answer [2] |
4 |
Halted |
0 ms |
0 KB |
- |