#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<pii,pii>pi2;
void solve(int n) {
//find index of value 1
int l=1;
int r=n;
int mid;
int one=1;
while(l<=r){
mid=(l+r)/2;
int hold=query(mid,n);
if(hold==n-1){
one=mid;
l=mid+1;;
}
else r=mid-1;
}
int ans[n+5];
memset(ans,-1,sizeof(ans));
ans[one]=1;
set<int>se;
for(int x=2;x<=n;x++){
se.insert(x);
}
//neighbour values
if(one>1){
ans[one-1]=1+query(one-1,one);
se.erase(ans[one-1]);
}
if(one<n){
ans[one+1]=1+query(one,one+1);
se.erase(ans[one+1]);
}
int st=1;
int ed=n;
if(one==1){
ed=n-1;
}
else st=2;
//recover other values
for(int x=one-2;x>=st;x--){
int a=query(x,x+1);
if(se.find(ans[x+1]+a)==se.end()&&se.find(ans[x+1]-a)!=se.end()){
ans[x]=ans[x+1]-a;
se.erase(ans[x]);
continue;
}
if(se.find(ans[x+1]+a)!=se.end()&&se.find(ans[x+1]-a)==se.end()){
ans[x]=ans[x+1]+a;
se.erase(ans[x]);
continue;
}
int b=query(x,x+2);
int diff=abs(ans[x+1]-ans[x+2]);
if(b==diff&&a<b){
//mid
if(ans[x+1]>ans[x+2]){
ans[x]=ans[x+1]-a;
}
else{
ans[x]=ans[x+1]+a;
}
}
else if(a==b){
if(ans[x+1]>ans[x+2]){
ans[x]=ans[x+1]-a;
}
else{
ans[x]=ans[x+1]+a;
}
}
else if(a>b){
if(ans[x+1]>ans[x+2]){
ans[x]=ans[x+1]-a;
}
else{
ans[x]=ans[x+1]+a;
}
}
else{
if(ans[x+2]>ans[x+1]){
ans[x]=ans[x+1]-a;
}
else{
ans[x]=ans[x+1]+a;
}
}
se.erase(ans[x]);
}
for(int x=one+2;x<=ed;x++){
int a=query(x-1,x);
if(se.find(ans[x-1]+a)==se.end()&&se.find(ans[x-1]-a)!=se.end()){
ans[x]=ans[x-1]-a;
se.erase(ans[x]);
continue;
}
if(se.find(ans[x-1]+a)!=se.end()&&se.find(ans[x-1]-a)==se.end()){
ans[x]=ans[x-1]+a;
se.erase(ans[x]);
continue;
}
int b=query(x-2,x);
int diff=abs(ans[x-1]-ans[x-2]);
if(b==diff&&a<b){
//mid
if(ans[x-1]>ans[x-2]){
ans[x]=ans[x-1]-a;
}
else{
ans[x]=ans[x-1]+a;
}
}
else if(a==b){
if(ans[x-1]>ans[x-2]){
ans[x]=ans[x-1]-a;
}
else{
ans[x]=ans[x-1]+a;
}
}
else if(a>b){
if(ans[x-1]>ans[x-2]){
ans[x]=ans[x-1]-a;
}
else{
ans[x]=ans[x-1]+a;
}
}
else{
if(ans[x-2]>ans[x-1]){
ans[x]=ans[x-1]-a;
}
else{
ans[x]=ans[x-1]+a;
}
}
se.erase(ans[x]);
}
for(int x=1;x<=n;x++){
if(ans[x]!=-1){
se.erase(se.find(ans[x]));
}
}
for(int x=1;x<=n;x++){
if(ans[x]==-1) ans[x]=*se.begin();
answer(x,ans[x]);
}
}
//code
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3046 ms |
344 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3046 ms |
344 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3046 ms |
344 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |