| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 236554 | LittleFlowers__ | 도서관 (JOI18_library) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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
#ifdef unx
int n;
int a[1111];
void Answer(const vector<int>&q){
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){
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();
}
l.push_back(i);
int to=tim(l);
if(l.size()==to+1){
l.pop_back();
dnc1(l,i);
dnc1(r,i);
} else if(l.size()==to){
dnc1(r,i);
} else{
l.pop_back();
dnc1(l,i);
}
}
vector<int> ad[1111];
void add(int i,int j){
ad[i].push_back(j);
ad[j].push_back(i);
}
void Solve(int 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;
dnc1(mp,i);
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