#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
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
int n;
vector<int> a;
vector<int> p;
/*
//grader
int query(int s, int t) {
int lo=1e9;
int hi=-1e9;
for (int i=s; i<=t; i++) {
lo=min(lo,p[i]);
hi=max(hi,p[i]);
}
return hi-lo;
}
void answer(int i, int a) {
assert(i>=1 && i<=n);
cout<<"a["<<i<<"]: "<<a<<endl;
assert(p[i]==a);
}
//end grader
*/
int ask(int x, int y) {
if (x>y) swap(x,y);
return query(x,y);
}
void solveRange(int l, int r, int idx, bool idxMax=true) {
if (l>=r) return;
//cout<<"["<<l<<" "<<r<<"] : "<<idx<<" "<<hi<<endl;
if (l+1==r) {
int dx = query(l,r);
if (idx==l) {
if (idxMax) a[r]=a[l]-dx; else a[r]=a[l]+dx;
answer(r,a[r]);
} else {
if (idxMax) a[l]=a[r]-dx; else a[l]=a[r]+dx;
answer(l,a[l]);
}
} else {
int d = query(l,r);
if (idx==l) {
// for (int i=r; i>=l; i--) {
// int dx=query(l,i);
// if (dx<d) {
// if (idxMax) a[i+1]=a[l]-d; else a[i+1]=a[l]+d;
// answer(i+1,a[i+1]);
// //l..i+1..r
// solveRange(l,i,l,idxMax);
// solveRange(i+1,r,i+1,!idxMax);
// return;
// }
// }
int lo=l;
int hi=r+1;
while (hi-lo>1) {
int mid=(hi+lo)/2;
if (query(l,mid)<d) {
lo=mid;
} else {
hi=mid;
}
}
//l..i+1..r
int i = lo;
if (idxMax) a[i+1]=a[l]-d; else a[i+1]=a[l]+d;
answer(i+1,a[i+1]);
solveRange(l,i,l,idxMax);
solveRange(i+1,r,i+1,!idxMax);
return;
} else {
// for (int i=l; i<=r; i++) {
// int dx=query(i,r);
// if (dx<d) {
// if (idxMax) a[i-1]=a[r]-d; else a[i-1]=a[r]+d;
// answer(i-1,a[i-1]);
// //l..i-1...r
// solveRange(l,i-1,i-1,!idxMax);
// solveRange(i,r,r,idxMax);
// return;
// }
// }
int lo=l-1;
int hi=r;
while (hi-lo>1) {
int mid=(lo+hi)/2;
if (query(mid,r)<d) {
hi=mid;
} else {
lo=mid;
}
}
int i=hi;
if (idxMax) a[i-1]=a[r]-d; else a[i-1]=a[r]+d;
answer(i-1,a[i-1]);
//l..i-1...r
solveRange(l,i-1,i-1,!idxMax);
solveRange(i,r,r,idxMax);
return;
}
assert(0);
}
}
void solve(int N) {
n = N;
a.resize(n+1, -1);
int nIdx=-1;
int lo=1;
int hi=n+1;
while (hi-lo>1) {
int mid=(hi+lo)/2;
if (query(1,mid)<n-1) {
lo=mid;
} else {
hi=mid;
}
}
nIdx=lo+1;
a[nIdx]=n;
answer(nIdx,a[nIdx]);
assert(nIdx>=1&&nIdx<=n);
solveRange(1,nIdx,nIdx);
solveRange(nIdx,n,nIdx);
}
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;
}
/*
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
for (int i=0; i<10; i++) {
int siz = 5;
p=rand_perm(siz);
//p={5,4,2,6,1,3};
//p={1,3,6,5,4,2};
p.insert(p.begin(), -1);
int lo=1,hi=1;
for (int i=1; i<=siz; i++) {
if (p[i]>p[hi]) hi=i;
if (p[i]<p[lo]) lo=i;
}
if (lo>hi) swap(p[lo],p[hi]);
for (int i: p) cout<<i<<" ";
cout<<endl;
solve(siz);
}
return 0;
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
6 ms |
256 KB |
Output is correct |
4 |
Correct |
7 ms |
256 KB |
Output is correct |
5 |
Correct |
10 ms |
256 KB |
Output is correct |
6 |
Correct |
7 ms |
256 KB |
Output is correct |
7 |
Correct |
6 ms |
256 KB |
Output is correct |
8 |
Correct |
6 ms |
256 KB |
Output is correct |
9 |
Correct |
8 ms |
384 KB |
Output is correct |
10 |
Correct |
9 ms |
256 KB |
Output is correct |
11 |
Correct |
8 ms |
384 KB |
Output is correct |
12 |
Correct |
7 ms |
256 KB |
Output is correct |
13 |
Correct |
7 ms |
256 KB |
Output is correct |
14 |
Correct |
8 ms |
384 KB |
Output is correct |
15 |
Correct |
7 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
6 ms |
256 KB |
Output is correct |
4 |
Correct |
7 ms |
256 KB |
Output is correct |
5 |
Correct |
10 ms |
256 KB |
Output is correct |
6 |
Correct |
7 ms |
256 KB |
Output is correct |
7 |
Correct |
6 ms |
256 KB |
Output is correct |
8 |
Correct |
6 ms |
256 KB |
Output is correct |
9 |
Correct |
8 ms |
384 KB |
Output is correct |
10 |
Correct |
9 ms |
256 KB |
Output is correct |
11 |
Correct |
8 ms |
384 KB |
Output is correct |
12 |
Correct |
7 ms |
256 KB |
Output is correct |
13 |
Correct |
7 ms |
256 KB |
Output is correct |
14 |
Correct |
8 ms |
384 KB |
Output is correct |
15 |
Correct |
7 ms |
256 KB |
Output is correct |
16 |
Correct |
12 ms |
256 KB |
Output is correct |
17 |
Correct |
19 ms |
384 KB |
Output is correct |
18 |
Correct |
25 ms |
384 KB |
Output is correct |
19 |
Correct |
33 ms |
256 KB |
Output is correct |
20 |
Correct |
28 ms |
256 KB |
Output is correct |
21 |
Correct |
28 ms |
256 KB |
Output is correct |
22 |
Correct |
30 ms |
256 KB |
Output is correct |
23 |
Correct |
80 ms |
256 KB |
Output is correct |
24 |
Correct |
81 ms |
500 KB |
Output is correct |
25 |
Correct |
71 ms |
384 KB |
Output is correct |
26 |
Correct |
27 ms |
256 KB |
Output is correct |
27 |
Correct |
35 ms |
256 KB |
Output is correct |
28 |
Correct |
30 ms |
256 KB |
Output is correct |
29 |
Correct |
31 ms |
256 KB |
Output is correct |
30 |
Correct |
29 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
6 ms |
256 KB |
Output is correct |
4 |
Correct |
7 ms |
256 KB |
Output is correct |
5 |
Correct |
10 ms |
256 KB |
Output is correct |
6 |
Correct |
7 ms |
256 KB |
Output is correct |
7 |
Correct |
6 ms |
256 KB |
Output is correct |
8 |
Correct |
6 ms |
256 KB |
Output is correct |
9 |
Correct |
8 ms |
384 KB |
Output is correct |
10 |
Correct |
9 ms |
256 KB |
Output is correct |
11 |
Correct |
8 ms |
384 KB |
Output is correct |
12 |
Correct |
7 ms |
256 KB |
Output is correct |
13 |
Correct |
7 ms |
256 KB |
Output is correct |
14 |
Correct |
8 ms |
384 KB |
Output is correct |
15 |
Correct |
7 ms |
256 KB |
Output is correct |
16 |
Correct |
12 ms |
256 KB |
Output is correct |
17 |
Correct |
19 ms |
384 KB |
Output is correct |
18 |
Correct |
25 ms |
384 KB |
Output is correct |
19 |
Correct |
33 ms |
256 KB |
Output is correct |
20 |
Correct |
28 ms |
256 KB |
Output is correct |
21 |
Correct |
28 ms |
256 KB |
Output is correct |
22 |
Correct |
30 ms |
256 KB |
Output is correct |
23 |
Correct |
80 ms |
256 KB |
Output is correct |
24 |
Correct |
81 ms |
500 KB |
Output is correct |
25 |
Correct |
71 ms |
384 KB |
Output is correct |
26 |
Correct |
27 ms |
256 KB |
Output is correct |
27 |
Correct |
35 ms |
256 KB |
Output is correct |
28 |
Correct |
30 ms |
256 KB |
Output is correct |
29 |
Correct |
31 ms |
256 KB |
Output is correct |
30 |
Correct |
29 ms |
256 KB |
Output is correct |
31 |
Correct |
55 ms |
384 KB |
Output is correct |
32 |
Correct |
75 ms |
384 KB |
Output is correct |
33 |
Incorrect |
80 ms |
384 KB |
Wrong Answer [2] |
34 |
Halted |
0 ms |
0 KB |
- |