# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1080203 | Tozzyyyy | Library (JOI18_library) | C++14 | 42 ms | 600 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 <cstdio>
#include <vector>
#include "library.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000;
vector<int> adj[MAXN];
vector<int> res;
int vs[MAXN];
void dfs(int u){
vs[u] = 1;
res.push_back(u);
for(auto x : adj[u]) if(vs[x] == 0) dfs(x);
}
void Solve(int n)
{
int lst = -1;
int cur = 1;
int cnt = 0;
while(cnt < n - 1){
vector<int> t;
for(int j = 1 ; j <= n ; j++){
if(cur == j or j == lst) continue;
t.push_back(j);
}
int l = 0 , r = t.size()-1;
int res = -1;
while(l <= r){
int mid = l + r >> 1;
vector<int> m(n);
for(int j = l ; j <=mid ; j++) m[t[j] - 1] = 1;
int c1 = Query(m);
m[cur-1] = 1;
int c2 = Query(m);
if(c2 <= c1) res = mid , r = mid-1;
else l = mid+1;
}
if(res == -1){
cur = 1;
lst = adj[1][0];
}else{
res = t[res];
adj[cur].push_back(res);
adj[res].push_back(cur);
lst = cur , cur = res, cnt++;
}
}
int mn = 2000;
for(int i = 1; i <= n ; i++){
mn = min(mn , (int)adj[i].size());
if(adj[i].size() == 1){
dfs(i);
break;
}
}
assert(mn == 1);
Answer(res);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |