Submission #969771

#TimeUsernameProblemLanguageResultExecution timeMemory
969771penguin133Park (JOI17_park)C++17
47 / 100
551 ms1160 KiB
#include <bits/stdc++.h> using namespace std; #include "park.h" //#define int long long #define pi pair<int, int> #define pii pair<int, pi> #define fi first #define se second #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); static int Place[1400], p2[1400]; const int szz = 8; void dnc(vector <int> shit){ if(shit.size() <= 1)return; if(shit.size() <= szz){ for(int i = 0; i < (int)shit.size(); i++){ for(int j = i + 1; j < (int)shit.size(); j++){ int x = shit[i], y = shit[j]; Place[x] = Place[y] = 1; if(x > y)swap(x, y); if(Ask(x, y, Place))Answer(x, y); Place[x] = Place[y] = 0; } } return; } vector <int> nxtstuff, die[7]; int bru = shit[rng()%shit.size()]; for(int i = 0; i < (int)shit.size(); i++){ if(shit[i] == bru)continue; Place[bru] = Place[shit[i]] = 1; int a = bru, b = shit[i]; if(a > b)swap(a, b); if(Ask(a, b, Place)){ nxtstuff.push_back(shit[i]); Answer(a, b); } Place[bru] = Place[shit[i]] = 0; } for(int i = 0; i < 1400; i++)p2[i] = 0; for(auto i : shit)p2[i] = 1; for(auto i : shit){ if(i == bru)continue; bool f = 0; for(auto j : nxtstuff)if(i == j)f = 1; if(f)continue; int lo = 0, hi = (int)nxtstuff.size() - 2, tmp = (int)nxtstuff.size() - 1; while(lo <= hi){ int mid = (lo + hi) >> 1; for(int k = mid + 1; k < (int)nxtstuff.size(); k++)p2[nxtstuff[k]] = 0; int a = bru, b = i; if(a > b)swap(a, b); int res = Ask(a, b, p2); for(auto k : nxtstuff)p2[k] = 1; if(res){ tmp = mid; hi = mid - 1; } else lo = mid + 1; } die[tmp].push_back(i); } for(int i = 0; i < (int)nxtstuff.size(); i++){ die[i].push_back(nxtstuff[i]); dnc(die[i]); } } set <int> adj[1405]; int sz[1405], block[1405], up[1405]; vector <pi> what; void comp(int x, int par){ sz[x] = 1; up[x] = par; for(auto i : adj[x])if(i != par && !block[i])comp(i, x), sz[x] += sz[i]; what.push_back({sz[x], x}); } void Detect(int T, int N) { if(T == 1){ for(int i = 0; i < N; i++){ for(int j = i + 1; j < N; j++){ Place[i] = Place[j] = 1; if(Ask(i, j, Place))Answer(i, j); Place[i] = Place[j] = 0; } } return; } /* vector <int> lol; for(int i = 0; i < N; i++)lol.push_back(i); shuffle(lol.begin(), lol.end(), rng); dnc(lol); */ vector <pi> fku; int val[N]; for(int i = 1; i < N; i++){ int lo = 0, hi = N - 1, tmp = hi; while(lo <= hi){ int mid = (lo + hi) >> 1; for(int j = 0; j <= mid; j++)Place[j] = 1; for(int j = mid + 1; j < N; j++)Place[j] = 0; Place[0] = Place[i] = 1; if(Ask(0, i, Place))tmp = mid, hi = mid - 1; else lo = mid + 1; } fku.push_back({tmp, i}); } sort(fku.begin(), fku.end()); for(auto [bb, i] : fku){ int hd = 0, res = -1; for(int j = 0; j < N; j++)block[j] = 0; while(1){ what.clear(); comp(hd, -1); if(sz[hd] == 1){ break; } sort(what.begin(), what.end()); pi bruh = {sz[hd] / 2, 0}; int tmp = lower_bound(what.begin(), what.end(), bruh) - what.begin(); if(tmp == (int)what.size())tmp--; int fin = (tmp ? (abs(what[tmp].fi - sz[hd] / 2) < abs(what[tmp - 1].fi - sz[hd] / 2) ? tmp : tmp - 1) : tmp); fin = what[fin].se; for(int a = 0; a < N; a++)Place[a] = 1; Place[fin] = 0; if(Ask(0, i, Place)){ //not in subtree block[fin] = 1; } else{ hd = fin; if(up[fin] != -1)block[up[fin]] = 1; } } int repl = -1; vector <int> bruh; for(auto j : adj[hd]){ for(int a = 0; a < N; a++)Place[a] = 1; Place[i] = 0; if(j && !Ask(0, j, Place)){ bruh.push_back(j); repl = j; } } if(!bruh.empty()){ for(auto a : bruh){ adj[hd].erase(a); adj[a].erase(hd); adj[i].insert(a); adj[a].insert(i); } adj[hd].insert(i); adj[i].insert(hd); } else adj[hd].insert(i), adj[i].insert(hd); } for(int i = 0; i < N; i++){ for(auto j : adj[i]){ //cout << j << ' '; if(j > i)Answer(i, j); } } }

Compilation message (stderr)

park.cpp: In function 'void Detect(int, int)':
park.cpp:115:15: warning: unused variable 'res' [-Wunused-variable]
  115 |   int hd = 0, res = -1;
      |               ^~~
park.cpp:140:7: warning: variable 'repl' set but not used [-Wunused-but-set-variable]
  140 |   int repl = -1;
      |       ^~~~
park.cpp:100:6: warning: unused variable 'val' [-Wunused-variable]
  100 |  int val[N];
      |      ^~~
#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...