//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
//#include "xylophone.h"
using namespace std;
using ll = long long;
using ld = long double;
const int N = 5000;
int a[N];
int b[N];
/*
int query(int l, int r) {
return *max_element(b + l - 1, b + r) - *min_element(b + l - 1, b + r);
}
*/
void solve(int n) {
int l = 1, r = n;
while (l + 1 < r) {
int mid = (l + r) / 2;
int t = query(1, mid);
if (t == n - 1) {
r = mid;
} else {
l = mid;
}
}
a[r] = n;
for (int i = r + 1; i <= n; i++) {
int t = query(i - 1, i);
if (a[i - 1] + t >= n) {
a[i] = a[i - 1] - t;
continue;
}
if (a[i - 1] - t < 1) {
a[i] = a[i - 1] + t;
continue;
}
int u = query(i - 2, i);
if (u == abs(a[i - 2] - a[i - 1])) {
if (a[i - 2] < a[i - 1]) {
a[i] = a[i - 1] - t;
} else {
a[i] = a[i - 1] + t;
}
continue;
}
if (u != t) {
int cand = a[i - 2] + u;
if (cand == a[i - 1] - t || cand == a[i - 1] + t) {
a[i] = cand;
} else {
a[i] = cand - 2 * u;
}
continue;
}
if (a[i - 2] < a[i - 1]) {
a[i] = a[i - 1] - t;
} else {
a[i] = a[i - 1] + t;
}
}
for (int i = r - 1; i >= 1; i--) {
int t = query(i, i + 1);
if (a[i + 1] + t >= n) {
a[i] = a[i + 1] - t;
continue;
}
if (a[i + 1] - t < 1) {
a[i] = a[i + 1] + t;
continue;
}
int u = query(i, i + 2);
if (u == abs(a[i + 2] - a[i + 1])) {
if (a[i + 2] < a[i + 1]) {
a[i] = a[i + 1] - t;
} else {
a[i] = a[i + 1] + t;
}
continue;
}
if (u != t) {
int cand = a[i + 2] + u;
if (cand == a[i + 1] - t || cand == a[i + 1] + t) {
a[i] = cand;
} else {
a[i] = cand - 2 * u;
}
continue;
}
if (a[i + 2] < a[i + 1]) {
a[i] = a[i + 1] - t;
} else {
a[i] = a[i + 1] + t;
}
}
for (int i = 1; i <= n; i++) {
answer(i, a[i]);
}
}
/*int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
iota(b, b + n, 1);
random_shuffle(b, b + n);
for (int i = 0; i < n; i++) {
cout << b[i] << " \n"[i + 1 == n];
}
solve(n);
return 0;
}*/
Compilation message
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:25:17: error: 'query' was not declared in this scope
int t = query(1, mid);
^~~~~
xylophone.cpp:34:17: error: 'query' was not declared in this scope
int t = query(i - 1, i);
^~~~~
xylophone.cpp:68:17: error: 'query' was not declared in this scope
int t = query(i, i + 1);
^~~~~
xylophone.cpp:102:9: error: 'answer' was not declared in this scope
answer(i, a[i]);
^~~~~~
xylophone.cpp:102:9: note: suggested alternative: 'assert'
answer(i, a[i]);
^~~~~~
assert
