#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);
//#define unx 1
#ifndef unx
#include "library.h"
#endif // unx
int n;
int mode;
#ifdef unx
int a[1111];
void Answer(const vector<int>&q){
//int has=0;
//forv(i,q) has|=!i;
//if(has || q.size()<n) cout<<0; else cout<<1;
//gg
forv(i,q) cout<<i<<" ";
gg
}
int Query(const vector<int>&q){
int has=0, tot=0;
forinc(i,1,n){
if(q[a[i]-1]){
tot+=!has;
has=1;
} else has=0;
}
return tot;
}
#endif // unx
int x[1111], y[1111], id[1111];
int root(int i){
return !id[i] ? i : id[i]=root(id[i]);
}
void join(int i,int j){
if((i=root(i))==(j=root(j))) return;
id[i]=j;
}
int tim(const vector<int>&q,int mode=1){
vector<int> fac(n), ask(n);
if(mode){
forv(i,q) fac[i-1]=1;
forinc(i,1,n) if(fac[root(i)-1]) ask[i-1]=1;
} else{
forv(i,q) ask[i-1]=1;
}
return Query(ask);
}
int dnc(vector<int> l,int i){
if(l.back()==i) l.pop_back();
if(l.size()<2) return l[0];
vector<int> r;
while(l.size()>r.size()){
r.push_back(l.back());
l.pop_back();
}
l.push_back(i);
return tim(l) < l.size() ? dnc(l,i) : dnc(r,i);
}
int pf,sf;
void dnc1(vector<int> l,int i,int has=2){
if(l.size()<2){
if(pf) sf=l[0]; else pf=l[0];
return;
}
vector<int> r;
while(l.size()>r.size()){
r.push_back(l.back());
l.pop_back();
}
if(mode){
//forv(t,l) cerr<<t<<" "; cerr<<":"<<has<<"\n";
//cerr<<(l.size()==to+1);
//1 2 3 4 = 2
}
l.push_back(i);
int to=tim(l);
if(l.size()==to+1){
l.pop_back();
dnc1(l,i,1);
if(has>1) dnc1(r,i,1);
} else if(l.size()==to){
dnc1(r,i,has);
} else{
l.pop_back();
dnc1(l,i,has);
}
}
vector<int> ad[1111];
void add(int i,int j){
ad[i].push_back(j);
ad[j].push_back(i);
}
void Solve(int N){
n=N;
vector<int> ask(n);
ask[0]=x[1]=y[1]=1;
vector<int> mp={1};
int tot=1;
forinc(i,2,n){
ask[i-1]=1;
int tmp=Query(ask);
if(tot<tmp){
mp.push_back(i);
x[i]=y[i]=i;
} else if(tot>tmp){
//cerr<<i<<"\n";
pf=sf=0;
if(i==4) mode=1;
dnc1(mp,i);
if(i==4){
//forv(j,mp) cerr<<j<<" ";
//cerr<<pf<<" "<<sf;
//gg
}
join(pf,i);
join(sf,i);
if(tim({x[pf],i},0)==1) add(x[pf],i), x[i]=y[pf]; else add(y[pf],i), y[i]=x[pf];
if(tim({x[sf],i},0)==1) add(x[sf],i), (x[i] ? y[i]=y[sf] : x[i]=y[sf]); else add(y[sf],i), (x[i] ? y[i]=x[sf] : x[i]=x[sf]);
fordec(i,mp.size()-1,0){
if(mp[i]==pf || mp[i]==sf){
swap(mp[i],mp.back());
mp.pop_back();
}
}
mp.push_back(i);
} else{
int to=dnc(mp,i);
join(i,to);
if(tim({x[to],i},0)==1){
add(i,x[to]);
x[to]=i;
} else{
add(i,y[to]);
y[to]=i;
}
}
//forv(j,mp) cerr<<j<<" "; cerr<<":"<<tmp<<"\n";
//cout<<"\n";
tot=tmp;
}
//forv(i,ad[10]) cerr<<i<<" ";
//gg
forinc(i,1,n){
if(ad[i].size()==1){
vector<int> ans={i};
int pre=-1;
forinc(j,2,n){
forv(t,ad[i]){
if(t!=pre){
ans.push_back(t);
pre=i;
i=t;
break;
}
}
}
Answer(ans);
gg
}
}
}
#ifdef unx
main(){
#define task "vim"
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
forinc(i,1,n=in) a[i]=in;
Solve(n);
}
#endif // unx
Compilation message
library.cpp: In function 'int dnc(std::vector<int>, int)':
library.cpp:83:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
return tim(l) < l.size() ? dnc(l,i) : dnc(r,i);
~~~~~~~^~~~~~~~~~
library.cpp: In function 'void dnc1(std::vector<int>, int, int)':
library.cpp:109:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(l.size()==to+1){
~~~~~~~~^~~~~~
library.cpp:113:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
} else if(l.size()==to){
~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
384 KB |
Unexpected end of file - token expected |
| 2 |
Incorrect |
21 ms |
384 KB |
Unexpected end of file - token expected |
| 3 |
Incorrect |
44 ms |
384 KB |
Unexpected end of file - token expected |
| 4 |
Incorrect |
24 ms |
384 KB |
Unexpected end of file - token expected |
| 5 |
Incorrect |
36 ms |
384 KB |
Unexpected end of file - token expected |
| 6 |
Incorrect |
27 ms |
384 KB |
Unexpected end of file - token expected |
| 7 |
Incorrect |
24 ms |
384 KB |
Unexpected end of file - token expected |
| 8 |
Incorrect |
24 ms |
384 KB |
Unexpected end of file - token expected |
| 9 |
Incorrect |
23 ms |
384 KB |
Unexpected end of file - token expected |
| 10 |
Incorrect |
16 ms |
420 KB |
Unexpected end of file - token expected |
| 11 |
Incorrect |
4 ms |
384 KB |
Wrong Answer [7] |
| 12 |
Incorrect |
4 ms |
384 KB |
Unexpected end of file - token expected |
| 13 |
Incorrect |
4 ms |
384 KB |
Unexpected end of file - token expected |
| 14 |
Incorrect |
4 ms |
384 KB |
Unexpected end of file - token expected |
| 15 |
Incorrect |
5 ms |
384 KB |
Unexpected end of file - token expected |
| 16 |
Incorrect |
6 ms |
384 KB |
Unexpected end of file - token expected |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
384 KB |
Unexpected end of file - token expected |
| 2 |
Incorrect |
21 ms |
384 KB |
Unexpected end of file - token expected |
| 3 |
Incorrect |
44 ms |
384 KB |
Unexpected end of file - token expected |
| 4 |
Incorrect |
24 ms |
384 KB |
Unexpected end of file - token expected |
| 5 |
Incorrect |
36 ms |
384 KB |
Unexpected end of file - token expected |
| 6 |
Incorrect |
27 ms |
384 KB |
Unexpected end of file - token expected |
| 7 |
Incorrect |
24 ms |
384 KB |
Unexpected end of file - token expected |
| 8 |
Incorrect |
24 ms |
384 KB |
Unexpected end of file - token expected |
| 9 |
Incorrect |
23 ms |
384 KB |
Unexpected end of file - token expected |
| 10 |
Incorrect |
16 ms |
420 KB |
Unexpected end of file - token expected |
| 11 |
Incorrect |
4 ms |
384 KB |
Wrong Answer [7] |
| 12 |
Incorrect |
4 ms |
384 KB |
Unexpected end of file - token expected |
| 13 |
Incorrect |
4 ms |
384 KB |
Unexpected end of file - token expected |
| 14 |
Incorrect |
4 ms |
384 KB |
Unexpected end of file - token expected |
| 15 |
Incorrect |
5 ms |
384 KB |
Unexpected end of file - token expected |
| 16 |
Incorrect |
6 ms |
384 KB |
Unexpected end of file - token expected |
| 17 |
Incorrect |
245 ms |
632 KB |
Unexpected end of file - token expected |
| 18 |
Incorrect |
234 ms |
512 KB |
Unexpected end of file - token expected |
| 19 |
Incorrect |
249 ms |
384 KB |
Unexpected end of file - token expected |
| 20 |
Incorrect |
209 ms |
384 KB |
Unexpected end of file - token expected |
| 21 |
Incorrect |
213 ms |
384 KB |
Unexpected end of file - token expected |
| 22 |
Incorrect |
241 ms |
544 KB |
Unexpected end of file - token expected |
| 23 |
Incorrect |
255 ms |
384 KB |
Unexpected end of file - token expected |
| 24 |
Incorrect |
90 ms |
384 KB |
Unexpected end of file - token expected |
| 25 |
Incorrect |
246 ms |
504 KB |
Unexpected end of file - token expected |
| 26 |
Incorrect |
207 ms |
384 KB |
Unexpected end of file - token expected |
| 27 |
Incorrect |
88 ms |
384 KB |
Unexpected end of file - token expected |
| 28 |
Incorrect |
56 ms |
384 KB |
Unexpected end of file - token expected |
| 29 |
Incorrect |
44 ms |
420 KB |
Unexpected end of file - token expected |
| 30 |
Incorrect |
52 ms |
464 KB |
Unexpected end of file - token expected |
