#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
// static int A[5000];
int pos = 1;
void get(int l, int r, int n){
if(l>=r)return;
int m = (l+r)/2;
if(query(m,n)==(n-1)) pos = m,get(m+1,r,n);
else get(l,m-1,n);
}
void solve(int n) {
vector<int>a(n+1);
get(1,n,n);
a[pos] = 1;
if(pos > 1)a[pos-1] = 1+query(pos-1,pos);
if(pos < n)a[pos+1] = 1+query(pos,pos+1);
vector<int>taken(n+1);
for(int i = pos-1;i<=pos+1;++i)taken[a[i]] = 1;
for(int i = pos-2;i>=1;--i){
set<int>opt;
int c = query(i,i+1);
if(a[i+1]-c >= 1 && !taken[a[i+1]-c])opt.insert(a[i+1]-c);
if(a[i+1]+c <= n && !taken[a[i+1]+c])opt.insert(a[i+1]+c);
if(opt.size()==1){
a[i] = *opt.begin();
taken[a[i]] = 1;
continue;
}
int v = abs(a[i+1]-a[i+2]);
int w = query(i,i+2);
if(w==v){
// a[i] lies between a[i+1] and a[i-1]
for(auto x : opt){
if(x >= min(a[i+1],a[i+2]) && x<= max(a[i+1],a[i+2])){
a[i] = x;
taken[x] = 1;
continue;
}
}
}else{
for(auto x : opt){
set<int>kk = {a[i+1],a[i+2],x};
if((*--kk.end())-*kk.begin() == w){
a[i] = x;
taken[x] = 1;
continue;
}
}
}
}
for(int i = pos+2;i<=n;++i){
set<int>opt;
int c = query(i-1,i);
if(a[i-1]-c >= 1 && !taken[a[i-1]-c])opt.insert(a[i-1]-c);
if(a[i-1]+c <= n && !taken[a[i-1]+c])opt.insert(a[i-1]+c);
if(opt.size()==1){
a[i] = *opt.begin();
taken[a[i]] = 1;
continue;
}
int v = abs(a[i-1]-a[i-2]);
int w = query(i-2,i);
if(w==v){
// a[i] lies between a[i-1] and a[i-2]
for(auto x : opt){
if(x >= min(a[i-1],a[i-2]) && x<= max(a[i-1],a[i-2])){
a[i] = x;
taken[x] = 1;
continue;
}
}
}else{
for(auto x : opt){
set<int>kk = {a[i-1],a[i-2],x};
if((*--kk.end())-*kk.begin() == w){
a[i] = x;
taken[x] = 1;
continue;
}
}
}
}
for(int i = 1;i<=n;++i){
answer(i,a[i]);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
1 ms |
208 KB |
Output is correct |
4 |
Correct |
2 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
208 KB |
Output is correct |
6 |
Correct |
2 ms |
208 KB |
Output is correct |
7 |
Incorrect |
1 ms |
208 KB |
Wrong Answer [7] |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
1 ms |
208 KB |
Output is correct |
4 |
Correct |
2 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
208 KB |
Output is correct |
6 |
Correct |
2 ms |
208 KB |
Output is correct |
7 |
Incorrect |
1 ms |
208 KB |
Wrong Answer [7] |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
1 ms |
208 KB |
Output is correct |
4 |
Correct |
2 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
208 KB |
Output is correct |
6 |
Correct |
2 ms |
208 KB |
Output is correct |
7 |
Incorrect |
1 ms |
208 KB |
Wrong Answer [7] |
8 |
Halted |
0 ms |
0 KB |
- |