| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 236607 | LittleFlowers__ | Library (JOI18_library) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
vector<int> vast;
#ifdef unx
int a[1111];
void Answer(const vector<int>&q){
/**
if(q.empty()){
cout<<0;
gg
}
if(q[0]!=vast[0]) reverse(all(vast));
cout<<(q==vast);
gg
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(n); ans[0]=i;
int pre=-1;
forinc(j,2,n){
forv(t,ad[i]){
if(t!=pre){
ans[j-1]=t;
pre=i;
i=t;
break;
}
}
}
vector<int> dup(n+1);
forv(i,ans){
if(++dup[i]>1)
exit(-1);
}
Answer(ans);
gg
}
}
}
#ifdef unx
main(){
#define task "library"
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
forinc(i,1,n=in) vast.push_back(a[i]=in);
Solve(n);
}
#endif // unx