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"
#include <bits/stdc++.h>
using namespace std;
static int A[5000];
void solve(int N) {
int lo = 1, hi = N-1;
int mini, maxi;
/*
cout << "START";
cout << endl;*/
while(query(lo, hi) == N-1) hi--;
maxi = hi+1;
while(query(lo, maxi) == N-1) lo++;
mini = lo-1;
//solve
vector<bool> found(N+1, false);
vector<int> ans(N+1, -1);
ans[mini] = 1;
ans[maxi] = N;
found[1] = found[N] = 1;
answer(mini, 1);
answer(maxi, N);
/*
cout << "MINI: " << mini << endl;
cout << "MAXI: " << maxi << endl;
cout.flush();*/
queue<int> q;
q.push(mini-1);
q.push(mini+1);
q.push(maxi-1);
q.push(maxi+1);
while(!q.empty()){
int curr = q.front();
q.pop();
if(curr < 1 || curr > N) continue;
if(ans[curr] >= 0) continue;
int prec = ans[curr-1] != -1 ? curr-1 : curr+1;
//cout << "CURR: " << curr << "\nPREC: " << prec << endl;
int diff = query(min(curr, prec), max(curr, prec));
if(ans[prec] + diff > N) ans[curr] = ans[prec] - diff;
else if(ans[prec] - diff < 1) ans[curr] = ans[prec] + diff;
else if(!found[ans[prec] - diff] && found[ans[prec] + diff]) ans[curr] = ans[prec] - diff;
else if(found[ans[prec] - diff] && !found[ans[prec] + diff]) ans[curr] = ans[prec] + diff;
else if(!found[ans[prec] - diff] && !found[ans[prec] + diff]){
// cout << "CURR: " << curr << "\nMINI: " << mini << endl;
int d2 = query(min(curr, mini), max(curr, mini));
if(d2 > diff) ans[curr] = ans[prec] + diff;
else ans[curr] = ans[prec] - diff;
}
found[ans[curr]] = 1;
//cout << "POS-" << curr << ": " << ans[curr] << endl;
answer(curr, ans[curr]);
cout.flush();
q.push(curr-1);
q.push(curr+1);
}
}
Compilation message (stderr)
xylophone.cpp:6:12: warning: 'A' defined but not used [-Wunused-variable]
static int A[5000];
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |