Submission #370262

#TimeUsernameProblemLanguageResultExecution timeMemory
370262Mamnoon_SiamPark (JOI17_park)C++17
67 / 100
2053 ms828 KiB
#include "park.h" #include <bits/stdc++.h> using namespace std; /* sorry, this is the bare minimum :'( */ using ll = long long; using ii = pair<int, int>; using vi = vector<int>; #define all(v) begin(v), end(v) #define sz(v) (int)(v).size() #define fi first #define se second const int N = 1500; using bs = bitset<N>; mt19937 rng(69); int random(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } vi diff(vi a, vi b) { sort(all(a)); sort(all(b)); vi r; set_difference(all(a), all(b), back_inserter(r)); return r; } static int Place[N]; bool ask(int u, int v, vi a) { if(u > v) swap(u, v); memset(Place, 0, sizeof Place); for(int i : a) Place[i] = 1; Place[u] = Place[v] = 1; return Ask(u, v, Place); } vector<ii> ans; void solve(vi s) { sort(all(s)); if(sz(s) <= 1) return; int x = random(0, sz(s)-1); int y = random(0, sz(s)-2); if(y >= x) ++y; x = s[x], y = s[y]; vi path; for(int z : s) if(z != x and z != y) { if(!ask(x, y, diff(s, {z}))) { path.emplace_back(z); } } vi tmp = path; sort(all(tmp)); sort(all(path), [&x,&path](int i, int j){ return !ask(x, j, diff(path, {i})); }); path.insert(path.begin(), x); path.emplace_back(y); vi notpath = diff(s, path); map<int, vi> mp; for(int u : notpath) { int lo = 1, hi = sz(path), opt = -1; while(lo <= hi) { int mid = (lo + hi) >> 1; if(ask(x, u, diff(s, vi(path.begin()+mid, path.end())))) { opt = mid; hi = mid-1; } else { lo = mid+1; } } mp[path[opt-1]].emplace_back(u); } for(int u : path) mp[u].emplace_back(u); for(int i = 1; i < sz(path); ++i) { ans.emplace_back(path[i-1], path[i]); } for(auto pa : mp) { solve(pa.se); } } void dumb(int n) { for(int i = 0; i < n; ++i) { for(int j = i+1; j < n; ++i) { if(ask(i, j, {i,j})) { Answer(i, j); } } } } void Detect(int T, int n) { if(T == 1) { dumb(n); return; } vi s(n); iota(all(s), 0); solve(s); for(ii x : ans) { if(x.fi > x.se) swap(x.fi, x.se); Answer(x.fi, x.se); } }
#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...