# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
768660 | raysh07 | Library (JOI18_library) | C++17 | 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>
#include "library.h"
using namespace std;
vector<vector<int>> adj;
vector<int> comp;
vector<bool> vis;
vector<int> m;
vector<int> deg;
int q = 0;
void init(int n){
for (int i = 0; i < n; i++) m[i] = 0;
}
int go(vector <int> m){
q++;
if (q > 20000) exit(0);
return Query(m);
}
bool check(int i, int j, int n){
if (i == j) return false;
for (int k = i; k <= j; k++){
m[k] = 1;
}
int cnt = 0;
for (auto x : adj[i]) m[x] = 0;
for (int i = 0; i < n; i++) cnt += m[i];
if (cnt == 1) {
init(n);
return false;
}
int a1 = go(m);
m[i] = 0;
int a2;
if (cnt != 2)
a2 = go(m);
else a2 = 1;
init(n);
return a2 >= a1;
}
void dfs(int u, int par = -1){
comp.push_back(u + 1);
vis[u] = true;
for (int v : adj[u]){
if (v != par){
assert(!vis[v]);
dfs(v, u);
}
}
}
void Solve(int n)
{
if (n == 1){
Answer({1});
return;
}
if (n == 2){
Answer({1, 2});
return;
}
m.resize(n, 0);
deg.resize(n, 0);
adj.resize(1e5 + 69);
vis.resize(1e5 + 69, false);
int ok = 0;
vector <int> m(n, 1);
vector <int> ok;
ok.push_back(1);
for (int i = 0; i < n; i++){
m[i] = 0;
if (i == n - 1){
ok.push_back(0);
} else if (i == n - 2){
ok.push_back(1);
} else {
ok.push_back(Query(m));
}
}
for (int i = 0; i < n; i++){
deg[i] = ok[i + 1] - ok[i] + 1;
}
for (int i = 0; i < n; i++){
int tm = 0;
while (tm < deg[i]){
int l = i + 1, r = n - 1;
while (l != r){
int m = (l + r)/2;
if (check(i, m, n)) r = m;
else l = m + 1;
}
ok++;
adj[i].push_back(l);
adj[l].push_back(i);
tm++;
}
}
for (int i = 0; i < n; i++){
if (adj[i].size() == 1){
dfs(i);
break;
}
}
assert(comp.size() == n);
Answer(comp);
}