| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 335026 |
2020-12-10T20:23:59 Z |
Plurm |
Library (JOI18_library) |
C++11 |
|
537 ms |
748 KB |
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int p[1024];
int fn(int x){
if(p[x] == -1) return x;
else return p[x] = fn(p[x]);
}
bool un(int x, int y){
x = fn(x);
y = fn(y);
if(x == y) return false;
p[x] = y;
return true;
}
int queryRange(int L, int R, int N, int sp = -1){
bitset<1024> s;
vector<int> M(N);
for(int i = L; i <= R; i++){
s[fn(i)] = true;
}
if(sp != -1) s[fn(sp)] = true;
for(int i = 0; i < N; i++){
if(s[fn(i)]) M[i] = 1;
else M[i] = 0;
}
return Query(M);
}
int countRange(int L, int R, int sp = -1){
bitset<1024> s;
for(int i = L; i <= R; i++){
s[fn(i)] = true;
}
if(sp != -1) s[fn(sp)] = true;
return s.count();
}
int LeftTurn(int L, int N){
// L -> x duplicates
// L -> x-1 does not duplicate
vector<int> active;
bitset<1024> s;
for(int i = L; i < N; i++){
int cur = fn(i);
if(!s[cur]){
active.push_back(i);
s[cur] = true;
}
}
if(queryRange(L, N-1, N, L) == countRange(L, N-1, L)) return -1;
int lo = 0;
int hi = active.size()-1;
int mid;
while(lo < hi){
mid = (lo + hi)/2;
if(queryRange(L, active[mid], N, L) == countRange(L, active[mid], L)) lo = mid+1;
else hi = mid;
}
return active[lo];
}
int RightTurn(int R, int N){
// x <- R duplicates
// x+1 <- R does not duplicate
vector<int> active;
bitset<1024> s;
for(int i = R; i >= 0; i--){
int cur = fn(i);
if(!s[cur]){
active.push_back(i);
s[cur] = true;
}
}
reverse(active.begin(), active.end());
if(queryRange(0, R, N, R) == countRange(0, R, R)) return -1;
int lo = 0;
int hi = active.size()-1;
int mid;
while(lo < hi){
mid = (lo + hi + 1)/2;
if(queryRange(active[mid], R, N, R) == countRange(active[mid], R, R)) hi = mid-1;
else lo = mid;
}
return active[lo];
}
vector<int> g[1024];
void addEdge(int u, int v){
g[u].push_back(v);
g[v].push_back(u);
}
int findLeaf(int u, int p = -1){
for(int v : g[u]){
if(v == p) continue;
return findLeaf(v, u);
}
return u;
}
pair<int,int> findExtremum(int u){
if(g[u].size() > 1){
return make_pair(findLeaf(g[u][0], u), findLeaf(g[u][1], u));
}else if(g[u].size() == 1){
return make_pair(u, findLeaf(g[u][0], u));
}else{
return make_pair(u, u);
}
}
bool checkPair(int l, int r, int N){
vector<int> M(N);
fill(M.begin(), M.end(), 0);
M[l] = M[r] = 1;
return Query(M) == 1;
//return g[l].size() < 2 && g[r].size() < 2;
}
void Solve(int N)
{
memset(p, -1, sizeof(p));
vector<int> M(N);
for(int i = 1; i < N; i++){
int l = LeftTurn(0, N);
int r = RightTurn(l, N);
int l1, l2;
tie(l1, l2) = findExtremum(l);
int r1, r2;
tie(r1, r2) = findExtremum(r);
if(checkPair(l1, r1, N)){
l = l1;
r = r1;
}else if(checkPair(l1, r2, N)){
l = l1;
r = r2;
}else if(checkPair(l2, r1, N)){
l = l2;
r = r1;
}else if(checkPair(l2, r2, N)){
l = l2;
r = r2;
}
un(l, r);
addEdge(l, r);
}
int last = -1;
int leaf = findLeaf(0);
vector<int> ans;
for(int i = 0; i < N; i++){
ans.push_back(leaf+1);
int nxt = -1;
for(int v: g[leaf]){
if(v != last) nxt = v;
}
last = leaf;
leaf = nxt;
}
Answer(ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
364 KB |
# of queries: 2812 |
| 2 |
Correct |
49 ms |
364 KB |
# of queries: 2807 |
| 3 |
Correct |
52 ms |
364 KB |
# of queries: 2978 |
| 4 |
Correct |
54 ms |
364 KB |
# of queries: 2971 |
| 5 |
Correct |
45 ms |
364 KB |
# of queries: 2948 |
| 6 |
Correct |
55 ms |
492 KB |
# of queries: 2918 |
| 7 |
Correct |
54 ms |
384 KB |
# of queries: 2950 |
| 8 |
Correct |
36 ms |
492 KB |
# of queries: 2805 |
| 9 |
Correct |
53 ms |
364 KB |
# of queries: 2961 |
| 10 |
Correct |
26 ms |
364 KB |
# of queries: 1749 |
| 11 |
Correct |
1 ms |
364 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
384 KB |
# of queries: 5 |
| 13 |
Correct |
1 ms |
364 KB |
# of queries: 12 |
| 14 |
Correct |
1 ms |
364 KB |
# of queries: 20 |
| 15 |
Correct |
2 ms |
364 KB |
# of queries: 117 |
| 16 |
Correct |
5 ms |
364 KB |
# of queries: 251 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
364 KB |
# of queries: 2812 |
| 2 |
Correct |
49 ms |
364 KB |
# of queries: 2807 |
| 3 |
Correct |
52 ms |
364 KB |
# of queries: 2978 |
| 4 |
Correct |
54 ms |
364 KB |
# of queries: 2971 |
| 5 |
Correct |
45 ms |
364 KB |
# of queries: 2948 |
| 6 |
Correct |
55 ms |
492 KB |
# of queries: 2918 |
| 7 |
Correct |
54 ms |
384 KB |
# of queries: 2950 |
| 8 |
Correct |
36 ms |
492 KB |
# of queries: 2805 |
| 9 |
Correct |
53 ms |
364 KB |
# of queries: 2961 |
| 10 |
Correct |
26 ms |
364 KB |
# of queries: 1749 |
| 11 |
Correct |
1 ms |
364 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
384 KB |
# of queries: 5 |
| 13 |
Correct |
1 ms |
364 KB |
# of queries: 12 |
| 14 |
Correct |
1 ms |
364 KB |
# of queries: 20 |
| 15 |
Correct |
2 ms |
364 KB |
# of queries: 117 |
| 16 |
Correct |
5 ms |
364 KB |
# of queries: 251 |
| 17 |
Correct |
513 ms |
684 KB |
# of queries: 19260 |
| 18 |
Correct |
494 ms |
496 KB |
# of queries: 18977 |
| 19 |
Correct |
515 ms |
748 KB |
# of queries: 19264 |
| 20 |
Correct |
459 ms |
620 KB |
# of queries: 17994 |
| 21 |
Correct |
437 ms |
492 KB |
# of queries: 16986 |
| 22 |
Correct |
522 ms |
504 KB |
# of queries: 19329 |
| 23 |
Correct |
537 ms |
492 KB |
# of queries: 19264 |
| 24 |
Correct |
205 ms |
364 KB |
# of queries: 8911 |
| 25 |
Correct |
483 ms |
492 KB |
# of queries: 18870 |
| 26 |
Correct |
446 ms |
556 KB |
# of queries: 17603 |
| 27 |
Correct |
165 ms |
492 KB |
# of queries: 8870 |
| 28 |
Correct |
355 ms |
424 KB |
# of queries: 12973 |
| 29 |
Correct |
359 ms |
560 KB |
# of queries: 12959 |
| 30 |
Correct |
329 ms |
620 KB |
# of queries: 12973 |
