#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
void solve(int N);
int query(int s, int t);
void answer(int i, int a);
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
int A[maxn];
void Set(int i, int a) {
answer(i,a);
A[i]=a;
}
void solve(int l, int r, bool big, int idx) {
if (r-l<=0) return;
if (idx==l) {
int gap=0;
int mid=-1;
for (int i=l+1; i<=r; i++) {
int res = query(l,i);
if (res>gap) {
gap=res;
mid=i;
}
}
assert(~mid);
// L....mid....r
if (big) {
Set(mid,A[idx]-gap);
solve(l,mid-1,true,l); // [l,mid)
solve(mid,r,false,mid); // [mid,r]
} else {
Set(mid,A[idx]+gap);
solve(l,mid-1,false,l); // [l,mid)
solve(mid,r,true,mid); // [mid,r]
}
} else if (idx==r) {
int gap=0;
int mid=-1;
for (int i=r-1; i>=l; i--) {
int res=query(i,r);
if (res>gap) {
gap=res;
mid=i;
}
}
assert(~mid);
// l....mid....R
if (big) {
Set(mid,A[idx]-gap);
solve(l,mid,false,mid); // [l,mid]
solve(mid+1,r,true,r); // (mid,r]
} else {
Set(mid,A[idx]+gap);
solve(l,mid,true,mid); // [l,mid]
solve(mid+1,r,false,r); // (mid,r]
}
} else {
assert(false);
}
}
void solve(int n) {
// find 1 and n
int i1 = -1;
int in = -1;
for (int i=1; in==-1 && i<=n; i++) {
for (int j=i; in==-1 && j<=n; j++) {
if (query(i,j)==n-1) {
in=j;
break;
}
}
}
assert(~in);
for (int j=in; i1==-1 && j>=1; j--) {
if (query(j,in)==n-1) {
i1=j;
break;
}
}
assert(~i1);
Set(i1,1);
Set(in,n);
solve(1,i1,false,i1);
solve(i1,in-1,false,i1);
solve(in,n,true,in);
// 1...i1.....in...n
}
int nn;
vector<int> v = {-1,4,6,5,1,7,3,2,9,8};
int query(int s, int t) {
assert(s<=t);
int mx=0;
for (int i=s; i<=t; i++) {
for (int j=i; j<=t; j++) {
mx=max(mx,abs(v[i]-v[j]));
}
}
return mx;
}
/*
void answer(int i, int a) {
A[i]=a;
}
void print() {
cout<<"v: ";
for (int i=1; i<=nn; i++) {
cout<<v[i]<<" ";
}
cout<<endl;
cout<<"A: ";
for (int i=1; i<=nn; i++) {
cout<<A[i]<<" ";
}
cout<<endl;
}
vector<int> rand_perm(int n, int index=1) {
assert(n>=1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> a(n);
iota(a.begin(), a.end(), index);
shuffle(a.begin(), a.end(), rng);
return a;
}
vector<int> genV(int n) {
vector<int> v = rand_perm(n, 1);
v.insert(v.begin(), -1);
int i1= -1; int in = -1;
for (int i=1; i<=n; i++) {
if (v[i]==1) i1=i;
if (v[i]==n) in=i;
}
if (i1>in) {
swap(v[i1],v[in]);
}
return v;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
v = genV(10);
nn = (int)v.size() - 1;
solve(nn);
print();
for (int i=1; i<=nn; i++) {
assert(A[i]==v[i]);
}
return 0;
}
*/
Compilation message
/tmp/ccGtv8bu.o: In function `query(int, int)':
grader.cpp:(.text+0x0): multiple definition of `query(int, int)'
/tmp/ccwDKdVd.o:xylophone.cpp:(.text+0x20): first defined here
collect2: error: ld returned 1 exit status
