| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 225953 |
2020-04-22T05:05:36 Z |
erd1 |
Park (JOI17_park) |
C++14 |
|
266 ms |
760 KB |
#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 == 1 || 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(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
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: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 time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
11 ms |
384 KB |
Output is correct |
| 3 |
Correct |
11 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
384 KB |
Wrong Answer[3] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
168 ms |
640 KB |
Output is correct |
| 2 |
Correct |
158 ms |
632 KB |
Output is correct |
| 3 |
Correct |
148 ms |
632 KB |
Output is correct |
| 4 |
Correct |
156 ms |
632 KB |
Output is correct |
| 5 |
Correct |
133 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
201 ms |
512 KB |
Output is correct |
| 2 |
Correct |
221 ms |
632 KB |
Output is correct |
| 3 |
Correct |
217 ms |
512 KB |
Output is correct |
| 4 |
Correct |
216 ms |
648 KB |
Output is correct |
| 5 |
Correct |
226 ms |
632 KB |
Output is correct |
| 6 |
Correct |
219 ms |
512 KB |
Output is correct |
| 7 |
Correct |
218 ms |
512 KB |
Output is correct |
| 8 |
Correct |
221 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
512 KB |
Output is correct |
| 2 |
Correct |
199 ms |
760 KB |
Output is correct |
| 3 |
Correct |
198 ms |
512 KB |
Output is correct |
| 4 |
Correct |
168 ms |
760 KB |
Output is correct |
| 5 |
Correct |
198 ms |
512 KB |
Output is correct |
| 6 |
Correct |
161 ms |
512 KB |
Output is correct |
| 7 |
Correct |
167 ms |
736 KB |
Output is correct |
| 8 |
Correct |
191 ms |
512 KB |
Output is correct |
| 9 |
Correct |
185 ms |
512 KB |
Output is correct |
| 10 |
Correct |
193 ms |
512 KB |
Output is correct |
| 11 |
Correct |
213 ms |
512 KB |
Output is correct |
| 12 |
Correct |
211 ms |
648 KB |
Output is correct |
| 13 |
Correct |
139 ms |
512 KB |
Output is correct |
| 14 |
Correct |
218 ms |
760 KB |
Output is correct |
| 15 |
Correct |
138 ms |
512 KB |
Output is correct |
| 16 |
Correct |
218 ms |
512 KB |
Output is correct |
| 17 |
Correct |
156 ms |
632 KB |
Output is correct |
| 18 |
Correct |
204 ms |
512 KB |
Output is correct |
| 19 |
Correct |
148 ms |
512 KB |
Output is correct |
| 20 |
Correct |
189 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
260 ms |
640 KB |
Output is correct |
| 2 |
Correct |
251 ms |
632 KB |
Output is correct |
| 3 |
Correct |
232 ms |
692 KB |
Output is correct |
| 4 |
Correct |
201 ms |
512 KB |
Output is correct |
| 5 |
Correct |
266 ms |
536 KB |
Output is correct |
| 6 |
Correct |
166 ms |
632 KB |
Output is correct |
| 7 |
Correct |
253 ms |
512 KB |
Output is correct |
| 8 |
Correct |
225 ms |
700 KB |
Output is correct |
| 9 |
Correct |
222 ms |
512 KB |
Output is correct |
| 10 |
Correct |
231 ms |
512 KB |
Output is correct |
| 11 |
Correct |
195 ms |
512 KB |
Output is correct |
| 12 |
Correct |
201 ms |
512 KB |
Output is correct |
| 13 |
Correct |
197 ms |
512 KB |
Output is correct |
| 14 |
Correct |
262 ms |
632 KB |
Output is correct |
| 15 |
Correct |
205 ms |
636 KB |
Output is correct |
| 16 |
Correct |
218 ms |
512 KB |
Output is correct |
| 17 |
Correct |
151 ms |
632 KB |
Output is correct |
| 18 |
Correct |
191 ms |
640 KB |
Output is correct |
