| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 582030 |
2022-06-23T09:43:53 Z |
MrDeboo |
Library (JOI18_library) |
C++17 |
|
1342 ms |
760 KB |
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
vector<pair<int,int>>vec;
int N,L,R,n;
int Slv(int x){
vector<int>vct[n];
for(auto &i:vec){
if(i.first>=L&&i.second<=R){
vct[i.first].push_back(i.second);
vct[i.second].push_back(i.first);
}
}
int ans=0;
vector<int>bl(n);
for(int i=0;i<n;i++){
if(bl[i]||vct[i].empty())continue;
int cnt=0;
deque<int>dq={i};
while(dq.size()){
int a=dq.front();
dq.pop_front();
if(bl[a])continue;
bl[a]=1;
cnt++;
for(auto &w:vct[a])dq.push_back(w);
}
ans++;
}
x-=ans;
int cnt=0;
for(int i=L;i<=R;i++){
if(!bl[i])cnt++;
}
return (x!=cnt);
}
int Range(int l,int r){
vector<int>v(n);
for(int w=l;w<=r;w++)v[w]=1;
L=l;
R=r;
return Slv(Query(v));
}
void Solve(int GGGG){
n=GGGG;
vector<int>res;
if(n==1){
res.push_back(1);
Answer(res);
return;
}
vector<int>vct[n];
N=exp2(ceil(log2(n)));
for(int i=0;i<n;i++){
while(vct[i].size()<2){
int l=i+1,r=n-1,mid,f=0;
while(l<=r){
mid=(l+r)/2;
if(Range(i,mid)){
r=mid-1;
f=mid;
}else l=mid+1;
}
if(f==0)break;
l=i;r=f-1;
int g=0;
while(l<=r){
mid=(l+r)/2;
if(Range(mid,f)){
l=mid+1;
g=mid;
}else r=mid-1;
}
vec.push_back({g,f});
vct[g].push_back(f);
vct[f].push_back(g);
}
}
deque<int>dq;
for(int i=0;i<n&&dq.empty();i++){
if(vct[i].size()==1)dq.push_back(i);
}
vector<bool>bl(n);
while(dq.size()){
int a=dq.front();
dq.pop_front();
if(bl[a])continue;
bl[a]=1;
res.push_back(a+1);
for(auto &i:vct[a])dq.push_back(i);
}
Answer(res);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
312 KB |
# of queries: 2798 |
| 2 |
Correct |
51 ms |
300 KB |
# of queries: 2794 |
| 3 |
Correct |
67 ms |
308 KB |
# of queries: 2939 |
| 4 |
Correct |
73 ms |
308 KB |
# of queries: 2915 |
| 5 |
Correct |
63 ms |
300 KB |
# of queries: 2951 |
| 6 |
Correct |
59 ms |
312 KB |
# of queries: 2911 |
| 7 |
Correct |
44 ms |
300 KB |
# of queries: 2935 |
| 8 |
Correct |
59 ms |
304 KB |
# of queries: 2788 |
| 9 |
Correct |
63 ms |
296 KB |
# of queries: 2915 |
| 10 |
Correct |
35 ms |
304 KB |
# of queries: 1720 |
| 11 |
Correct |
0 ms |
208 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
208 KB |
# of queries: 3 |
| 13 |
Correct |
1 ms |
208 KB |
# of queries: 7 |
| 14 |
Correct |
1 ms |
208 KB |
# of queries: 14 |
| 15 |
Correct |
2 ms |
208 KB |
# of queries: 111 |
| 16 |
Correct |
4 ms |
208 KB |
# of queries: 245 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
312 KB |
# of queries: 2798 |
| 2 |
Correct |
51 ms |
300 KB |
# of queries: 2794 |
| 3 |
Correct |
67 ms |
308 KB |
# of queries: 2939 |
| 4 |
Correct |
73 ms |
308 KB |
# of queries: 2915 |
| 5 |
Correct |
63 ms |
300 KB |
# of queries: 2951 |
| 6 |
Correct |
59 ms |
312 KB |
# of queries: 2911 |
| 7 |
Correct |
44 ms |
300 KB |
# of queries: 2935 |
| 8 |
Correct |
59 ms |
304 KB |
# of queries: 2788 |
| 9 |
Correct |
63 ms |
296 KB |
# of queries: 2915 |
| 10 |
Correct |
35 ms |
304 KB |
# of queries: 1720 |
| 11 |
Correct |
0 ms |
208 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
208 KB |
# of queries: 3 |
| 13 |
Correct |
1 ms |
208 KB |
# of queries: 7 |
| 14 |
Correct |
1 ms |
208 KB |
# of queries: 14 |
| 15 |
Correct |
2 ms |
208 KB |
# of queries: 111 |
| 16 |
Correct |
4 ms |
208 KB |
# of queries: 245 |
| 17 |
Correct |
1265 ms |
632 KB |
# of queries: 19272 |
| 18 |
Correct |
1221 ms |
504 KB |
# of queries: 19023 |
| 19 |
Correct |
1227 ms |
484 KB |
# of queries: 19236 |
| 20 |
Correct |
1178 ms |
492 KB |
# of queries: 18001 |
| 21 |
Correct |
1072 ms |
484 KB |
# of queries: 16942 |
| 22 |
Correct |
1263 ms |
512 KB |
# of queries: 19274 |
| 23 |
Correct |
1342 ms |
524 KB |
# of queries: 19249 |
| 24 |
Correct |
338 ms |
344 KB |
# of queries: 8900 |
| 25 |
Correct |
1213 ms |
524 KB |
# of queries: 18825 |
| 26 |
Correct |
1068 ms |
624 KB |
# of queries: 17607 |
| 27 |
Correct |
315 ms |
320 KB |
# of queries: 8854 |
| 28 |
Correct |
840 ms |
760 KB |
# of queries: 18953 |
| 29 |
Correct |
829 ms |
640 KB |
# of queries: 18932 |
| 30 |
Correct |
909 ms |
632 KB |
# of queries: 18953 |
