| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 145002 | osaaateiasavtnl | 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;
mt19937 rnd(228);
vector <int> ans, pos;
int N;
#ifdef HOME
int Q = 0;
int Query(vector <int> m) {
if (m.size() == 1) return 1;
++Q;
vector <bool> used(N);
for (int i = 0; i < N; ++i) {
if (m[i]) used[pos[i]] = 1;
}
int ans = 0;
for (int i = 0; i < N; ++i) {
ans += used[i] && (!i || !used[i - 1]);
}
return ans;
}
void Answer(vector <int> a) {
cout << "Q = " << Q << '\n';
auto b = a; reverse(b.begin(), b.end());
if (a == ans || b == ans) cout << "correct\n";
else {
for (int e : ans) cout << e << ' '; cout << '\n';
for (int e : a) cout << e << ' '; cout << '\n';
cout << "WA\n";
exit(0);
}
}
#else
#include "library.h"
#endif
#define ii pair <int, int>
#define app push_back
// Query()
// Answer()
vector <ii> ed;
vector <int> g[1001];
int query(vector<int> v) {
vector<int> m(N,0);
for(int i:v) m[i]=1;
return Query(m);
}
int new_edge(vector <int> v) {
int ans = v.size() - query(v);
vector<int> m(N,0);
for(int i:v) m[i]=1;
for (auto e : ed) ans -= m[e.first] && m[e.second];
return ans;
}
void Solve(int n) {
Q = 0;
N = n;
for (int i = 0; i < 1001; ++i) g[i].clear();
ed.clear();
for (int t = 0; t < n - 1; ++t) {
vector <int> cur;
for (int i = 0; i < n; ++i) cur.app(i);
while (cur.size() > 2) {
int m = (cur.size() + 1) >> 1;
while (1) {
shuffle(cur.begin(), cur.end(), rnd);
vector <int> l, r;
for (int i = 0; i < m; ++i) l.app(cur[i]);
for (int i = m; i < cur.size(); ++i) r.app(cur[i]);
if (new_edge(l)) {
cur = l;
break;
}
if (new_edge(r)) {
cur = r;
break;
}
}
}
ed.app({cur[0], cur[1]});
g[cur[0]].app(cur[1]); g[cur[1]].app(cur[0]);
}
vector <int> ans;
for (int i = 0; i < n; ++i) {
if (g[i].size() != 2) {
ans.app(i); break;
}
}
int p = -1;
for (int i = 0; i < n - 1; ++i) {
for (int v : g[ans.back()]) {
if (v != p) {
p = ans.back();
ans.app(v);
break;
}
}
}
for (auto &e : ans) ++e;
Answer(ans);
}
#ifdef HOME
int main() {
int t = 10;
while (t--) {
int N = 1000;
ans.clear();
pos.resize(N);
for (int i = 1; i <= N; ++i) ans.app(i);
shuffle(ans.begin(), ans.end(), rnd);
for (int i = 0; i < N; ++i) pos[ans[i] - 1] = i;
Solve(N);
}
}
#endif