| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 320975 | mhy908 | 자동 인형 (IOI18_doll) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "doll.h"
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;
int n, m, arr[200010], cnt[100010], num[200010];
vector<int> vc[100010], ret1, ret2, ret3;
int conn[100010], re, sp[30][200010];
pii sw[200010];
void make_tree(int nw, int k, int nwnum, int rt, int skp, int lg, int tot, int c){
if(k==2){
int l=sp[lg][nwnum], r=sp[lg][nwnum+1];
if(l<=skp)sw[nw].F=rt;
else sw[nw].F=vc[c][l-skp-1];
if(r<=skp)sw[nw].S=rt;
else sw[nw].F=vc[v][r-skp-1];
return;
}
re+=2;
sw[nw]=mp(-re+1, -re);
make_tree(sw[nw].F, k/2, nwnum, rt, skp, lg, tot, c);
make_tree(sw[nw].S, k/2, nwnum+k/2, rt, skp, lg, tot, c);
}
void create_circuit(int M, vector<int> A){
n=A.size(); m=M;
for(int i=0; i<n; i++)arr[i+1]=A[i];
for(int i=1; i<=n; ++){
num[i]=++cnt[arr[i]];
if(i!=n)vc[arr[i]].eb(arr[i+1]);
else vc[arr[i]].eb(0);
}
sp[0][1]=1;
for(int j=1; j<20; j++){
for(int i=1; i<=(1<<j); i+=2)sp[j][i]=sp[j-1][2*i-1];
for(int i=2; i<=(1<<j); i+=2)sp[j][i]=sp[j][i-1]+(1<<(j-1));
}
conn[0]=arr[1];
for(int i=1; i<=m; i++){
if(!cnt[i])continue;
if(cnt[i]==1){
conn[i]=vc[i][0];
continue;
}
int sz, lg;
for(sz=1, lg=0; sz<cnt[i]; sz*=2, lg++);
++re;
conn[i]=-re;
make_tree(++re, sz, 1, -re, sz-cnt[i], lg, sz, i);
}
for(int i=0; i<=m; i++)ret1.eb(conn[i]);
for(int i=1; i<=re; i++)ret2.eb(sw[i].F);
for(int i=1; i<=re; i++)ret3.eb(sw[i].S);
answer(ret1, ret2, ret3);
}