Submission #1209000

#TimeUsernameProblemLanguageResultExecution timeMemory
1209000mychecksedadPark (JOI17_park)C++20
0 / 100
31 ms580 KiB
/* Author : Mychecksdead */ #include "park.h" #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; static int Place[1400]; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rng(34236234); int rn(int l, int r){ return uniform_int_distribution<int>(l,r)(rng); } int n; bool ask(int a, int b, vi u){ for(int i = 0; i < n; ++i) Place[i] = 0; if(a > b) swap(a, b); Place[a] = 1; Place[b] = 1; for(int x: u) Place[x] = 1; return Ask(a, b, Place); } bool ask2(int a, int b, vi u){ for(int i = 0; i < n; ++i) Place[i] = 1; for(int x: u) Place[x] = 0; if(a > b) swap(a, b); return Ask(a, b, Place); } void answer(int a, int b){ if(a>b) swap(a, b); // cerr << a << ' ' << b << '\n'; Answer(a, b); } void chain_solver(vector<int> nodes){ if(nodes.size() <= 1) return; // cerr << "chain solve: "; // for(int x: nodes) cerr << x << ' '; // cerr << '\n'; int v = nodes[rn(0, int(nodes.size())-1)]; vector<vi> C; vector<int> U; for(int u: nodes){ if(u != v){ bool is = ask(u, v, vi{}); if(is){ answer(u, v); C.pb(vi{u}); U.pb(u); } } } for(int u: nodes){ bool is = 0; for(int x: U) is = is | (x == u); if(u != v && !is){ int l = 0, r = int(U.size()) - 2, res = int(U.size()) - 1; while(l <= r){ int mid = l+r>>1; vi to_pop; for(int i = 0; i <= mid; ++i) to_pop.pb(U[i]); if(ask2(v, u, to_pop) == 0){ res = mid; r = mid - 1; }else{ l = mid + 1; } } C[res].pb(u); } } for(auto &V: C){ chain_solver(V); } } void solve(vector<int> nodes){ if(nodes.size() <= 1) return; // cerr << "solve: "; // for(int x: nodes) cerr << x << ' '; // cerr << '\n'; if(nodes.size() == 2){ answer(nodes[0], nodes[1]); return; } // int v = nodes[0];//nodes[rn(0, int(nodes.size())-1)]; int A = nodes[rn(0, int(nodes.size()) - 1)]; int B = nodes[rn(0, int(nodes.size()) - 1)]; while(B == A){ B = nodes[rn(0, int(nodes.size()) - 1)]; } // cerr << A << ' ' << B << '\n'; vi cur = nodes; vector<vi> C; vector<int> U; while(cur.size()){ int v = cur.back(); cur.pop_back(); if(v == A || v == B) continue; if(ask2(A, B, vi{v}) == 0){ // its in C.pb({}); U.pb(v); } } chain_solver(U); if(U.size()){ if(ask(A, U[0], vi{}) == 0) reverse(all(U)), reverse(all(C)); answer(A, U[0]); answer(B, U.back()); }else{ answer(A, B); } C.insert(C.begin(), vi{}); U.insert(U.begin(), A); C.pb({}); U.pb(B); // cerr << "U :"; // for(int x: U) cerr << x << ' '; // cerr << '\n'; // cerr << A << ' ' << B << '\n'; for(int u: nodes){ bool is = false; for(int x: U) is = is | (x == u); if(is) continue; int l = 0, r = int(U.size()) - 2, res = int(U.size()) - 1; while(l <= r){ int mid = l+r>>1; vi to_pop = {U[mid]}; if(ask2(B, u, to_pop)){ l = mid + 1; }else{ res = mid; r = mid - 1; } } // cerr << res << ' ' << u << '\n'; C[res].pb(u); } for(int i = 0; i < int(U.size()); ++i){ // for(int u: C[i]){ // if(ask(u, U[i], vi{})){ // answer(u, U[i]); // break; // } // } C[i].pb(U[i]); } for(auto V: C){ solve(V); } } void Detect(int t, int nn) { n = nn; vi v; for(int i = 1; i <= n; ++i){ v.pb(i-1); } solve(v); }
#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...