#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
void solve(int N){
vector<int> A(N + 1) , e(N + 1);
int x = 0 , y = 0;
for(int bit = 12;bit >= 0;bit --){
if(y + (1 << bit) <= N){
if(query(1 , y + (1 << bit)) < N - 1){
y += (1 << bit);
}
}
}
++y;
for(int bit = 12;bit >= 0;bit --){
if(x + (1 << bit) <= y){
if(query(x + (1 << bit) , y) == N - 1){
x += (1 << bit);
}
}
}
e[1] = 1;
e[N] = 1;
A[x] = 1;
A[y] = N;
auto bad = [&](int v){
if(v < 1 || v > N){
return 1;
}
return e[v];
};
for(int i = x - 1;i >= 1;i --){
int v = query(i , i + 1);
if(bad(A[i + 1] - v)){
A[i] = A[i + 1] + v;
e[A[i]] = 1;
continue;
}
if(bad(A[i + 1] + v)){
A[i] = A[i + 1] - v;
e[A[i]] = 1;
continue;
}
int u = query(i , i + 2);
if(A[i + 1] < A[i + 2]){
if(u == A[i + 2] - A[i + 1]){
A[i] = A[i + 1] + v;
}else{
if(u == v){
A[i] = A[i + 1] + v;
}else{
A[i] = A[i + 2] - v;
}
}
}else{
if(u == A[i + 1] - A[i + 2]){
A[i] = A[i + 1] - v;
}else{
if(v == u){
A[i] = A[i + 2] - v;
}else{
A[i] = A[i + 1] + v;
}
}
}
e[A[i]] = 1;
}
for(int i = x + 1;i <= N;i ++){
if(i == y){
continue;
}
int v = query(i - 1 , i);
if(bad(A[i - 1] - v)){
A[i] = A[i - 1] + v;
e[A[i]] = 1;
continue;
}
if(bad(A[i - 1] + v)){
A[i] = A[i - 1] - v;
e[A[i]] = 1;
continue;
}
int u = query(i - 2 , i);
if(A[i - 1] < A[i - 2]){
if(u == A[i - 2] - A[i - 1]){
A[i] = A[i - 1] + v;
}else{
if(u == v){
A[i] = A[i - 1] + v;
}else{
A[i] = A[i - 1] - v;
}
}
}else{
if(u == A[i - 1] - A[i - 2]){
A[i] = A[i - 1] - v;
}else{
if(v == u){
A[i] = A[i - 1] - v;
}else{
A[i] = A[i - 1] + v;
}
}
}
e[A[i]] = 1;
}
for(int i = 1;i <= N;i ++){
answer(i , A[i]);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [7] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [7] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [7] |
4 |
Halted |
0 ms |
0 KB |
- |