Submission #225954

#TimeUsernameProblemLanguageResultExecution timeMemory
225954erd1Park (JOI17_park)C++14
90 / 100
279 ms768 KiB
#include "park.h" #include<bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define pb push_back using namespace std; typedef pair<int, int> pii; template<typename Iter> ostream& outIt(ostream& out, Iter b, Iter e){ for(Iter i = b; i != e; i++) out << (i == b?"":" ") << *i; return out; } template<typename T> ostream& operator<<(ostream& out, vector<T>& v){ return outIt(out << '[', all(v)) << ']'; } template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2> v){ return out << "(" << v.first << ", " << v.second << ")"; } static int Place[1400]; int ran(int t = INT_MAX){ static int x = 10292837; return ((x*0xdefaced+1)&INT_MAX)%t; } bool ask(int l, int r){ //cout << l << " " << r << endl; for(int i = 0; i < 6; i++)cout << Place[i] << " "; cout << endl; return Ask(min(l, r), max(l, r), Place); } void answer(int l, int r){ //cout << l << " a " << r << endl; Answer(min(l, r), max(l, r)); } void Sort(int l, int r, vector<int>& v){ ////cout << l << " " <<r << " " << v<< endl; if(v.size() == 0) return answer(l, r); if(v.size() == 1) return answer(l, v[0]), answer(v[0], r); int pivot = v[ran(v.size())]; for(auto i: v)Place[i] = 1; Place[l] = Place[r] = 1; vector<int> R, L; for(auto i: v) if(i != pivot) Place[i] = 0, (ask(l, pivot)?R:L).pb(i), Place[i] = 1; for(auto i: v)Place[i] = 0; Place[l] = Place[r] = 0; Sort(l, pivot, L); Sort(pivot, r, R); auto st = copy(all(L), v.begin()); *st = pivot; copy(all(R), next(st)); } int FindLink(int N, int x, vector<int> v){ int l = 0, r = v.size(); ////cout << "FindLink" << v << endl; for(int i = 0; i < N; i++)Place[i] = 1; while(r-l > 1){ for(int i = (l+r>>1); i < v.size();i++)Place[v[i]] = 0; (ask(v[0], x)?r:l) = l+r>>1; for(int i = 0; i < v.size();i++)Place[v[i]] = 1; } for(int i = 0; i < N; i++)Place[i] = 0; return v[l]; } vector<int> Findchain(int x, int y, vector<int>& pool){ ////cout << "Findchain" << endl; Place[x] = Place[y] = 1; vector<int> ans; if(ask(x, y))return Place[x] = Place[y] = 0, ans; int l = -1, r = pool.size(); while(true){ while(r-l > 1){ for(auto i: pool)Place[i] = false; for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = 1; (ask(x, y)?r:l) = (l+r>>1); } if(r == 0)break; ans.pb(pool[r-1]); Place[pool[r-1]] = 1; pool.erase(pool.begin()+r-1); l = -1; } for(auto i: pool)Place[i] = false; for(auto i: ans)Place[i] = false; Place[x] = Place[y] = 0; reverse(all(ans)); return ans; } vector<vector<int>> G; void MakePool(int p, int x, vector<int>& v){ v.pb(p); for(auto i: G[p])if(i != x)MakePool(i, x, v); } void CheckEdge(int x, int p, int b){ //cout << pool << endl; vector<int> pool; MakePool(p, b, pool); //cout << "Check " << x << " " << p << " " << b << " " << pool << endl; for(auto i: pool)Place[i] = true; Place[x] = true; if(!ask(x, p)){ for(auto i: pool)Place[i] = 0; Place[x] = 0; return; } //cout << "incheck" << endl; for(auto i: pool)Place[i] = 0; Place[x] = Place[p] = true; vector<int> pend; if(ask(x, p)) { answer(x, p); //cout << "found " << p << " " << x << endl; Place[x] = Place[p] = false; pend.pb(p); }else while(true){ int l = 0, r = pool.size()+1; while(r-l > 1){ for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = 1; (ask(x, p)?r:l) = (l+r>>1); for(auto i: pool)Place[i] = false; } //cout << l << " " << r << endl; if(l == pool.size())break; answer(pool[l], x); pend.pb(pool[l]); pool.erase(pool.begin()+l); } Place[x] = false; for(auto i: pend)for(auto ii: G[i])CheckEdge(x, ii, b); } void badcheck(int i, int j){ Place[i] = Place[j] = true; if(ask(i, j))answer(i, j); Place[i] = Place[j] = false; } vector<int> v, ord, pool; vector<bool> used; void Detect(int T, int N) { v.resize(N-1); G.resize(N); iota(all(v), 1); pool.resize(N-1); iota(all(pool), 1); used.resize(N); ord.pb(0); random_shuffle(all(v), ran); ////cout << v << endl; for(auto i: v){ if(used[i])continue; int x = FindLink(N, i, ord); // maybe i -> (>x) pool.erase(find(all(pool), i)); auto vs = Findchain(x, i, pool); //cout << x << " " << i << vs << endl; for(auto j: vs)used[j] = true; Sort(x, i, vs); vs.pb(i); //cout << x << " " << vs << endl; if(T == 5) //for(int it = find(all(ord), x)-ord.begin()+1; it < ord.size(); it++) for(auto j: vs)for(auto i: G[x])CheckEdge(j, i, x); if(T == 1) for(int it = find(all(ord), x)-ord.begin()+1; it < ord.size(); it++) for(auto j: vs)badcheck(ord[it], j); if(x)for(auto j: vs)CheckEdge(j, 0, x); for(int j = 0, last = x; j < vs.size(); j++)G[last].pb(vs[j]), last = vs[j]; //cout << G << endl; copy(all(vs), inserter(ord, ord.end())); //cout << ord << endl; vs.resize(0); } }

Compilation message (stderr)

park.cpp: In function 'int FindLink(int, int, std::vector<int>)':
park.cpp:66:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         for(int i = (l+r>>1); i < v.size();i++)Place[v[i]] = 0;
                      ~^~
park.cpp:66:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = (l+r>>1); i < v.size();i++)Place[v[i]] = 0;
                               ~~^~~~~~~~~~
park.cpp:67:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         (ask(v[0], x)?r:l) = l+r>>1;
                              ~^~
park.cpp:68:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v.size();i++)Place[v[i]] = 1;
                        ~~^~~~~~~~~~
park.cpp: In function 'std::vector<int> Findchain(int, int, std::vector<int>&)':
park.cpp:82:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = 1;
                                 ~^~
park.cpp:83:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             (ask(x, y)?r:l) = (l+r>>1);
                                ~^~
park.cpp: In function 'void CheckEdge(int, int, int)':
park.cpp:108:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(auto i: pool)Place[i] = true; Place[x] = true;
     ^~~
park.cpp:108:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(auto i: pool)Place[i] = true; Place[x] = true;
                                       ^~~~~
park.cpp:110:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for(auto i: pool)Place[i] = 0; Place[x] = 0;
         ^~~
park.cpp:110:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         for(auto i: pool)Place[i] = 0; Place[x] = 0;
                                        ^~~~~
park.cpp:126:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = 1;
                                 ~^~
park.cpp:127:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             (ask(x, p)?r:l) = (l+r>>1);
                                ~^~
park.cpp:131:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(l == pool.size())break;
            ~~^~~~~~~~~~~~~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:168:62: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int it = find(all(ord), x)-ord.begin()+1; it < ord.size(); it++)
                                                           ~~~^~~~~~~~~~~~
park.cpp:171:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0, last = x; j < vs.size(); j++)G[last].pb(vs[j]), last = vs[j];
                                  ~~^~~~~~~~~~~
#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...