// #include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define endl "\n"
const int mod=1e9+7;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
template <typename T> istream& operator>>(istream& is, vector<T> &a) {
copy_n(istream_iterator<T>(is), a.size(), a.begin()); return is;}
#ifdef IOI
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
const int mxn=2e5+100;
static int A[5000];
#ifdef IOI
static const int N_MAX = 5000;
static const int Q_MAX = 10000;
static int N;
// static int A[N_MAX];
static bool used[N_MAX];
static int query_c;
static int answer_c;
int query(int s, int t) {
if(query_c >= Q_MAX) {
printf("Wrong Answer\n");
exit(0);
}
query_c++;
if(!(1 <= s && s <= t && t <= N)) {
printf("Wrong Answer\n");
exit(0);
}
int mx = 0, mn = N + 1;
for(int i = s - 1; i < t; i++) {
if(mx < A[i]) {
mx = A[i];
}
if(mn > A[i]) {
mn = A[i];
}
}
return mx - mn;
}
void answer(int i, int a) {
answer_c++;
if(!(1 <= i && i <= N)) {
printf("Wrong Answer\n");
exit(0);
}
if(!(1 <= a && a <= N)) {
printf("Wrong Answer\n");
exit(0);
}
if(used[i - 1]) {
printf("Wrong Answer\n");
exit(0);
}
if(a != A[i - 1]) {
printf("Wrong Answer\n");
exit(0);
}
used[i - 1] = true;
}
#endif
void solve(int N) {
int n=N;
int x=query(1,n);
vector<int> ans(n+1);
int l=1;
int r=n;
int pos=-1;
while(l<=r){
int mid=(l+r)/2;
dbg(l,mid,r,query(mid,n),x)
if(query(mid,n)==x){
pos=mid;
l=mid+1;
}else{
r=mid-1;
}
}
bool visited[n+1];
memset(visited,false,sizeof(visited));
ans[pos]=1;
visited[1]=1;
if(pos!=n){
ans[pos+1]=query(pos,pos+1)+1;//b-a=q => b=q+a
visited[ans[pos+1]]=1;
for(int i=pos+2;i<=n;i++){
int a=ans[i-2];
int b=ans[i-1];
int x=query(i-2,i);
int y=query(i-1,i);
for(int c=1;c<=n;c++){
if(visited[c]) continue;
vector<int> v={a,b,c};
sort(all(v));
vector<int> t={b,c};
sort(all(t));
if(v[2]-v[0]==x&&t[1]-t[0]==y){
ans[i]=c;
visited[ans[i]]=1;
break;
}
}
}
}
if(pos!=1){
ans[pos-1]=query(pos-1,pos)+1;
for(int i=pos-2;i>=1;i--){
int a=ans[i+2];
int b=ans[i+1];
int x=query(i,i+2);
int y=query(i,i+1);
for(int c=1;c<=n;c++){
if(visited[c]) continue;
vector<int> v={a,b,c};
sort(all(v));
vector<int> t={b,c};
sort(all(t));
if(v[2]-v[0]==x&&t[1]-t[0]==y){
ans[i]=c;
visited[ans[i]]=1;
break;
}
}
}
}
for(int i=1;i<=n;i++){
answer(i,ans[i]);
}
// dbg(ans)
}
#ifdef IOI
// #include <cstdio>
// #include <cstdlib>
// #include "xylophone.h"
int main() {
query_c = 0;
answer_c = 0;
if(scanf("%d", &N) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
for(int i = 0; i < N; i++) {
if(scanf("%d", A + i) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
used[i] = false;
}
solve(N);
if(!(answer_c == N)) {
printf("Wrong Answer\n");
exit(0);
}
printf("Accepted : %d\n", query_c);
}
#endif
Compilation message
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:79:8: error: 'query' was not declared in this scope
79 | int x=query(1,n);
| ^~~~~
xylophone.cpp:18:18: warning: statement has no effect [-Wunused-value]
18 | #define dbg(...) 1337;
| ^~~~
xylophone.cpp:86:3: note: in expansion of macro 'dbg'
86 | dbg(l,mid,r,query(mid,n),x)
| ^~~
xylophone.cpp:142:3: error: 'answer' was not declared in this scope
142 | answer(i,ans[i]);
| ^~~~~~
xylophone.cpp: At global scope:
xylophone.cpp:25:12: warning: 'A' defined but not used [-Wunused-variable]
25 | static int A[5000];
| ^
