| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 533976 | michao | Xylophone (JOI18_xylophone) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "xylophone.h"
#define int long long
using namespace std;
const int MAX=5e3+5;
int ans[MAX];
bool zajety[MAX];
int n;
/*
int query(int l,int r){
cout<<"? "<<l<<" "<<r<<endl;
int rsp;
cin>>rsp;
return rsp;
}
void answer(){
cout<<"! ";
for (int i=1;i<=n;i++)cout<<ans[i]<<" ";
cout<<endl;
}*/
bool check(int x){
return x>=1 && x<=n && !zajety[x];
}
void solve(int N){
/*
n=N;
int ip=1,ik=n;
while (ip+1<ik){
int mid=(ip+ik)>>1;
if (query(1,mid)==n-1)ik=mid;
else ip=mid;
}
int r=ik;
ik=r,ip=1;
while (ip+1<ik){
int mid=(ip+ik)>>1;
if (query(mid,r)==n-1)ip=mid;
else ik=mid;
}
int l=ip;
ans[l]=1,ans[r]=n;
zajety[1]=true;
zajety[n]=true;
for (int i=l-1;i>=1;i--){
if (i==l-1){
int probuj=query(i,l)+ans[l];
ans[i]=probuj;
zajety[ans[i]]=true;
}
else{
int q1=query(i,i+1); // poprzedni
int q2=query(i,i+2); // przedpoprzedni
int a=ans[i+2];
int b=ans[i+1];
if (a<b){
if (check(b+q1) && b+q1==q2+a){
ans[i]=b+q1;
}
else ans[i]=b-q1;
}
else{
if (check(b-q1) && b-q1==a-q2){
ans[i]=b-q1;
}
else ans[i]=b+q1;
}
}
zajety[ans[i]]=true;
}
for (int i=l+1;i<=r-1;i++){
if (i==l+1){
int probuj=query(l,i)+ans[l];
ans[i]=probuj;
zajety[ans[i]]=true;
}
else{
int q1=query(i-1,i); // poprzedni
int q2=query(i-2,i); // przedpoprzedni
int a=ans[i-2];
int b=ans[i-1];
if (a<b){
if (check(b+q1) && b+q1==q2+a){
ans[i]=b+q1;
}
else ans[i]=b-q1;
}
else{
if (check(b-q1) && b-q1==a-q2){
ans[i]=b-q1;
}
else ans[i]=b+q1;
}
}
zajety[ans[i]]=true;
}
for (int i=r+1;i<=n;i++){
if (i==r+1){
int probuj=ans[r]-query(r,i);
ans[i]=probuj;
zajety[ans[i]]=true;
}
else{
int q1=query(i-1,i); // poprzedni
int q2=query(i-2,i); // przedpoprzedni
int a=ans[i-2];
int b=ans[i-1];
if (a<b){
if (check(b+q1) && b+q1==q2+a){
ans[i]=b+q1;
}
else ans[i]=b-q1;
}
else{
if (check(b-q1) && b-q1==a-q2){
ans[i]=b-q1;
}
else ans[i]=b+q1;
}
}
zajety[ans[i]]=true;
}
for (int i=1;i<=n;i++)answer(i,ans[i]);*/
}
/*
int32_t main(){
BOOST;
cin>>n;
int ip=1,ik=n;
while (ip+1<ik){
int mid=(ip+ik)>>1;
if (query(1,mid)==n-1)ik=mid;
else ip=mid;
}
int r=ik;
ik=r,ip=1;
while (ip+1<ik){
int mid=(ip+ik)>>1;
if (query(mid,r)==n-1)ip=mid;
else ik=mid;
}
int l=ip;
ans[l]=1,ans[r]=n;
zajety[1]=true;
zajety[n]=true;
for (int i=l-1;i>=1;i--){
if (i==l-1){
int probuj=query(i,l)+ans[l];
ans[i]=probuj;
zajety[ans[i]]=true;
}
else{
int q1=query(i,i+1); // poprzedni
int q2=query(i,i+2); // przedpoprzedni
int a=ans[i+2];
int b=ans[i+1];
if (a<b){
if (check(b+q1) && b+q1==q2+a){
ans[i]=b+q1;
}
else ans[i]=b-q1;
}
else{
if (check(b-q1) && b-q1==a-q2){
ans[i]=b-q1;
}
else ans[i]=b+q1;
}
}
zajety[ans[i]]=true;
}
for (int i=l+1;i<=r-1;i++){
if (i==l+1){
int probuj=query(l,i)+ans[l];
ans[i]=probuj;
zajety[ans[i]]=true;
}
else{
int q1=query(i-1,i); // poprzedni
int q2=query(i-2,i); // przedpoprzedni
int a=ans[i-2];
int b=ans[i-1];
if (a<b){
if (check(b+q1) && b+q1==q2+a){
ans[i]=b+q1;
}
else ans[i]=b-q1;
}
else{
if (check(b-q1) && b-q1==a-q2){
ans[i]=b-q1;
}
else ans[i]=b+q1;
}
}
zajety[ans[i]]=true;
}
for (int i=r+1;i<=n;i++){
if (i==r+1){
int probuj=ans[r]-query(r,i);
ans[i]=probuj;
zajety[ans[i]]=true;
}
else{
int q1=query(i-1,i); // poprzedni
int q2=query(i-2,i); // przedpoprzedni
int a=ans[i-2];
int b=ans[i-1];
if (a<b){
if (check(b+q1) && b+q1==q2+a){
ans[i]=b+q1;
}
else ans[i]=b-q1;
}
else{
if (check(b-q1) && b-q1==a-q2){
ans[i]=b-q1;
}
else ans[i]=b+q1;
}
}
zajety[ans[i]]=true;
}
answer();
return 0;
}
*/