# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
496608 | ignaciocanta | Xylophone (JOI18_xylophone) | C++14 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
void solve(int n) {
int low = 1, high = n;
while(high - low > 1){
int mid = low + (high - low) / 2;
if(query(1, mid) == n - 1) high = mid;
else low = mid;
}
int posN = high;
low = 1, high = n;
while(high - low > 1){
int mid = low + (high - low) / 2;
if(query(mid, n) == n - 1) low = mid;
else high = mid;
}
vector<set<int>> cands(n+1);
vector<bool> seen(n+1, 0), use(n+1, 0);
cands[posN].insert(n);
cands[low].insert(1);
int tot = 0;
while(tot < n){
int todo = -1;
for(int i = 1; i <= n; ++i){
if(int(cands[i].size()) == 1 && !use[i]){
todo = *cands[i].begin();
use[i] = 1;
//cout << "En " << i << " va " << todo << "\n";
answer(i, *cands[i].begin());