제출 #296496

#제출 시각아이디문제언어결과실행 시간메모리
296496BTheroPark (JOI17_park)C++17
10 / 100
186 ms1048 KiB
// chrono::system_clock::now().time_since_epoch().count() #include "park.h" #include<bits/stdc++.h> #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define all(x) (x).begin(), (x).end() #define debug(x) cerr << #x << " = " << x << endl; using namespace std; typedef long long ll; typedef pair<int, int> pii; mt19937 rnd(chrono::system_clock::now().time_since_epoch().count()); static int tmp_arr[2005]; static int n; bool ask(int a, int b, vector<int> &vec) { if (a > b) { swap(a, b); } fill(tmp_arr, tmp_arr + n, 0); for (int x : vec) { tmp_arr[x] = 1; } return Ask(a, b, tmp_arr); } void report(int a, int b) { if (a > b) { swap(a, b); } Answer(a, b); } namespace subtask1 { void solve() { for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { vector<int> S; S.pb(i); S.pb(j); if (ask(i, j, S)) { report(i, j); } } } } }; namespace subtask2 { vector<int> calc(int L, int R, vector<int> S) { vector<int> ret; if (S.size() == 2) { ret.pb(L); ret.pb(R); return ret; } int m = rnd() % S.size(); while (S[m] == L || S[m] == R) { m = rnd() % S.size(); } int M = S[m]; vector<int> A, B; A.pb(L); A.pb(M); B.pb(M); B.pb(R); for (int x : S) { if (x != L && x != M && x != R) { vector<int> S2 = S; S2.erase(find(all(S2), x)); if (ask(L, M, S2)) { B.pb(x); } else { A.pb(x); } } } A = calc(L, M, A); B = calc(M, R, B); for (int x : A) { ret.pb(x); } ret.pop_back(); for (int x : B) { ret.pb(x); } return ret; } void solve() { vector<int> S; for (int i = 0; i < n; ++i) { S.pb(i); } S = calc(0, n - 1, S); for (int i = 0; i + 1 < n; ++i) { report(S[i], S[i + 1]); } } }; namespace subtask3 { vector<vector<int>> f(vector<int> S, int v) { S.erase(find(all(S), v)); vector<vector<int>> comp; for (int x : S) { vector<int> tmp; tmp.pb(v); tmp.pb(x); if (ask(v, x, tmp)) { report(v, x); comp.pb(vector<int>(1, x)); } } vector<int> T = S; for (vector<int> vec : comp) { S.erase(find(all(S), vec[0])); } for (int x : S) { int p = 0; vector<int> perm(comp.size()); iota(all(perm), 0); //random_shuffle(all(perm)); while (p + 1 < (int)comp.size() && !ask(comp[perm[p]][0], x, T)) { ++p; } comp[perm[p]].pb(x); } return comp; } void go(vector<int> sub) { if ((int)sub.size() == 1) { return; } if ((int)sub.size() == 2) { report(sub[0], sub[1]); return; } int v = sub[rnd() % (int)sub.size()]; vector<vector<int>> comp = f(sub, v); vector<int> others = sub; others.erase(find(all(others), v)); for (vector<int> vec : comp) { others.erase(find(all(others), vec[0])); } if (others.size() > 5) { int u = others[rnd() % (int)others.size()]; vector<vector<int>> comp2 = f(sub, u), comp3; int ptr_v = 0, ptr_u = 0; while (find(all(comp[ptr_v]), u) == comp[ptr_v].end()) { ++ptr_v; } while (find(all(comp2[ptr_u]), v) == comp2[ptr_u].end()) { ++ptr_u; } vector<int> used(n + 5, 0); for (int i = 0; i < (int)comp.size(); ++i) { if (i != ptr_v) { comp3.pb(comp[i]); for (int x : comp[i]) { used[x] = 1; } } } for (int i = 0; i < (int)comp2.size(); ++i) { if (i != ptr_u) { comp3.pb(comp2[i]); for (int x : comp[i]) { used[x] = 1; } } } vector<int> ext; for (int x : sub) { if (x != u && x != v && !used[x]) { ext.pb(x); } } comp3.pb(ext); comp = comp3; } for (vector<int> nsub : comp) { go(nsub); } } void solve() { vector<int> S; for (int i = 0; i < n; ++i) { S.pb(i); } go(S); } }; void Detect(int T, int N) { n = N; if (T == 1) { subtask1::solve(); } else { subtask3::solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...