| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 329207 | NachoLibre | Library (JOI18_library) | 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;
#include "library.h"
/*int p[100] = {5, 3, 4, 1, 2};
int Query(vector<bool> v, int x) {
}*/
const int N = 1003;
int e[N][2];
vector<bool> qv;
int ask(vector<int> v) {
for(int i = 0; i < qv.size(); ++i) qv[i] = 0;
for(int i = 0; i < v.size(); ++i) qv[v[i] - 1] = 1;
return Query(qv);
}
bool neig(vector<int> v, int x) {
int a = ask(v);
v.push_back(x);
int b = ask(v);
v.pop_back();
return(a >= b);
}
void dvd(vector<int> &v, int x) {
int n = v.size();
vector<int> l;
for(int i = 0; i < n / 2; ++i) {
l.push_back(v[i]);
}
if(neig(l, x)) v = l;
else {
l.clear();
for(int i = n / 2; i < n; ++i) {
l.push_back(v[i]);
}
v = l;
}
}
void Solve(int n) {
qv.resize(n);
vector<int> v;
for(int i = 2; i <= n; ++i) {
v.push_back(i);
}
int dg = 1;
while(true) {
vector<int> u = v;
while(u.size() > 1) {
dvd(u, dg);
}
if(neig(u, dg)) {
e[dg][0] = u[0];
e[u[0]][1] = dg;
dg = u[0];
v.erase(find(v.begin(), v.end(), u[0]));
} else {
break;
}
}
dg = 1;
while(v.size()) {
vector<int> u = v;
while(u.size() > 1) {
dvd(u, dg);
}
e[dg][1] = u[0];
e[u[0]][0] = dg;
dg = u[0];
v.erase(find(v.begin(), v.end(), u[0]));
}
dg = 1;
while(e[dg][0]) dg = e[dg][0];
while(dg) {
v.push_back(dg);
dg = e[dg][1];
}
Answer(v);
}
/*int main() {
ios::sync_with_stdio(0);
cin.tie(0);
return 0;
}*/