Submission #370257

#TimeUsernameProblemLanguageResultExecution timeMemory
370257Mamnoon_SiamPark (JOI17_park)C++17
67 / 100
2059 ms964 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; /*set<int> st(all(a)); for(int x : b) { st.erase(x); } return vi(all(st));*/ } 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); } // bs onlyi[N]; 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); } } // static int Place[1400]; void Detect(int T, int n) { // for(int i = 0; i < n; ++i) onlyi[i][i] = 1; 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); } /*int i; for(i = 0 ; i < 2 ; i++) Place[i] = 0; for(i = 2 ; i < N ; i++) Place[i] = 1; if(Ask(3, 5, Place) != 1) return; Answer(2, 4); Answer(2, 5); Answer(3, 4); Place[0] = 1; Place[3] = 0; Place[5] = 0; if(Ask(0, 4, Place) != 0) return; Answer(0, 1); Answer(0, 3); Answer(1, 4); Answer(1, 2);*/ }
#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...