| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 595097 | TimDee | 자동 인형 (IOI18_doll) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "doll.h"#include <bits/stdc++.h>using namespace std; struct tree {int n, size;vector<int> t, x, y, state;void build(int N, int amt) {n=N;size=1;while ((size<<1)<n) size<<=1;t.assign(2*size-1,0), x.assign(2*size-1,0), y.assign(2*size-1,0), state.assign(2*size-1,0);for (int i=1; i<=size-1; ++i) {x[i-1] = -(2*i);y[i-1] = -(2*i+1);}int cnt=0, p=0;while (cnt<2*size-amt) {if (p>=size-1) {if (state[p]) {y[p]=-1;} else {x[p]=-1;}state[p]^=1;++cnt;p=0;continue;}if (!state[p]) {state[p]^=1;p<<=1; ++p;} else {state[p]^=1;++p; p<<=1;}}}}; void create_circuit(int m, vector<int>a) {int n=a.size();vector<int> cnt(m+1,0);int mx=0;for (int i=0; i<n; ++i) {cnt[a[i]]++;mx=max(mx,cnt[a[i]]);}if (mx==1) {vector<int> c(m+1,0);c[0]=a[0];for (int i=1; i<n; ++i) {c[a[i-1]]=a[i];}vector<int> x(0), y(0);answer(c,x,y);} else if (mx==2) {vector<vector<int>> next(m+1);//vector<int> b=a;a.push_back(0);for (int i=0; i<n; ++i) next[a[i]].push_back(a[i+1]);vector<int> c(m+1);c[0]=a[0];for (int i=1; i<=m; ++i) {c[i]=-i;}vector<int> x(m,0), y(m,0);for (int i=1; i<=m; ++i) {if (!next[i].size()) continue;x[i-1] = next[i].size()>1 ? next[i][0] : -(i);y[i-1] = next[i].size()>1 ? next[i][1] : next[i][0];}//if (cnt[a[n-1]]==2) {// //} else {////}answer(c,x,y);} else if (n==16) { vector<int> c(m+1,-1); c[0]=a[0]; vector<int> x(15), y(15); for (int i=0;i<7;++i) {x[i]=-(2*i+2); y[i]=-(2*i+3);} x[7]=a[1], x[11]=a[2], x[9]=a[3], x[13]=a[4], x[8]=a[5], x[12]=a[6], x[10]=a[7], x[14]=a[8];Y[7]=a[9], y[11]=a[10], y[9]=a[11], y[13]=a[12], y[8]=a[13], y[12]=a[14], y[10]=a[15], y[14]=0;answer(c,x,y);} else if (m==1) { int size=1;while (4*size<n) size<<=1;vector<int> x(2*size+1), y(2*size+1), state(2*size+1,0), c = {1, -(2*size)};for (int i=1; i<=size-1; ++i) {x[i-1] = -(2*i);y[i-1] = -(2*i+1);}x[2*size-1]=-(2*size+1);y[2*size-1]=-1;x[2*size] = y[2*size] = 1; int cnt=0, p=0;while (cnt<2*size) { //cout<<p<<"->";if (p>=size-1) {//cout<<"added "<<p<<' '<<cnt<<'\n';if (state[p]) {if (cnt<n-1-2*size) y[p]=1;else y[p]=-(2*size);} else {if (cnt<n-1-2*size) x[p]=1;else x[p]=-(2*size);}state[p]^=1;++cnt;p=0;continue;} if (!state[p]) { state[p]^=1;p<<=1; ++p; } else { state[p]^=1;++p; p<<=1; } }y[2*size-2]=0;answer(c,x,y); } else { vector<int> c(m+1),x,y;c[0]=a[0];vector<tree> v(m+1);for (int i=1; i<=m; ++i) v[i].build(cnt[i],cnt[i]); int in=0, p=0;while (in<n) {int ind = a[in];while (p<v[ind].size-1) {if (!v[ind].state[p]) {v[ind].state[p]^=1;p<<=1;++p;} else {v[ind].state[p]^=1;++p;p<<=1;}}if (!v[ind].state[p]) {v[ind].x[p]= ((++in)<n) ? a[in] : 0;v[ind].state[p]^=1;} else {v[ind].y[p]= ((++in)<n) ? a[in] : 0;v[ind].state[p]^=1;}p=0;} for(int i=1; i<=m; ++i) {int sz=x.size();for (auto X:v[i].x) x.push_back( X>=0 ? X : (X-sz) );for (auto Y:v[i].y) y.push_back( Y>=0 ? Y : (Y-sz) );c[i]=-1-sz;}answer(c,x,y); }}