Submission #429573

#TimeUsernameProblemLanguageResultExecution timeMemory
429573lycPark (JOI17_park)C++14
100 / 100
540 ms808 KiB
#include "park.h" #include <bits/stdc++.h> using namespace std; #define TRACE(x) cerr << #x << " :: " << x << endl #define _ << " " << #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(),(x).end() #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define RFOR(i,a,b) for(int i=(a);i>=(b);--i) static int Place[1400]; const int mxN = 1405; vector<int> solved, rem, stk, al[mxN]; int N, ban[mxN], vis[mxN]; void myans(int i, int j) { //TRACE("ANSWER" _ i _ j); if (i > j) swap(i,j); al[i].push_back(j); al[j].push_back(i); Answer(i,j); } bool myask(int i, int j, vector<int> v) { if (i > j) swap(i,j); v.push_back(i); v.push_back(j); for (int& x : v) Place[x] = 1; int ret = Ask(i,j,Place); for (int& x : v) Place[x] = 0; return ret; } void solveLine(int l, int r) { //TRACE("LINE" _ l _ r); vector<int> line; line.push_back(l); line.push_back(r); while (l != r) { int u = *(++find(ALL(line),l)); while (true) { //TRACE("CHECK" _ l _ u); if (myask(l,u,solved)) { l = u; break; } int lo = -1, hi = SZ(rem); while (hi-lo > 1) { int mid = (lo+hi)/2; vector<int> v2(solved); FOR(i,0,mid) v2.push_back(rem[i]); if (myask(l,u,v2)) hi = mid; else lo = mid; } u = rem[hi]; assert(find(ALL(rem),u) != rem.end()); rem.erase(find(ALL(rem),u)); line.insert(find(ALL(line),l)+1,u); } } //cerr << "line: "; for (int& x : line) { cerr << x << ' '; } cerr << endl; //cerr << "rem: "; for (int& x : rem) { cerr << x << ' '; } cerr << endl; line.pop_back(); for (int& x : line) stk.push_back(x); } void dfs(int u, vector<int>& cc) { vis[u] = 1; cc.push_back(u); for (int& v : al[u]) if (!ban[v] && !vis[v]) dfs(v,cc); } void solveComp(int u, vector<int> cc) { //TRACE("COMP" _ u _ SZ(cc)); //for (int& x : cc){ cout << x << ' '; } cout << endl; int lo = -1, hi = SZ(cc); while (hi-lo > 1) { int mid = (lo+hi)/2; vector<int> v2; FOR(i,0,mid) v2.push_back(cc[i]); if (myask(u,cc[0],v2)) hi = mid; else lo = mid; } int v = cc[hi]; myans(u,v); ban[v] = 1; fill_n(vis,N,0); vector<vector<int>> vcc; for (int& x : cc) if (!ban[x] && !vis[x]) { vector<int> comp; dfs(x,comp); if (myask(u,comp[0],comp)) vcc.push_back(comp); } for (auto& comp : vcc) solveComp(u,comp); } void Detect(int T, int _N) { N = _N; solved.push_back(0); FOR(i,1,N-1) rem.push_back(i); while (SZ(solved) < N) { if (!SZ(stk)) stk.push_back(rem.back()), rem.pop_back(); int u = stk.back(); stk.pop_back(); //TRACE("CHECK" _ u _ solved[0]); //for (int& x : solved){ cout << x << ' '; } cout << endl; if (!myask(u,solved[0],solved)) { solveLine(u,solved[0]); } else { fill_n(ban,N,0); solveComp(u,solved); solved.push_back(u); } //TRACE("OK"); } }
#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...