| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 362446 | David_M | Unscrambling a Messy Bug (IOI16_messy) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "messy.h"
#define pb push_back
using namespace std;
string s;
vector<int> Ans(128);
int A[128*4];
vector <int> v, V;
int sz[7], f[128];
bool g[7][7];
void buildA(int x=1, int l=0, int r=128, int y=0){
if(y==7)return;
for (int i=max(l, 7); i<r; i++)
A[x]+=(!(i&(1<<(6-y))));
buildA(x<<1, l, l+r>>1, y+1);
buildA(x<<1|1, l+r>>1, r, y+1);
}
void add(int x,int y=-1){ s[x]='1';if(y>=0)s[y]='1'; add_element(s, x, y); s[x]='0';if(y>=0)s[y]='0';}
bool check(int x,int y=-1){s[x]='1';if(y>=0)s[y]='1';bool b=check_element(s);s[x]='0';if(y>=0)s[y]='0';return b;}
void ADD(){
for (int i=0; i<7; i++)add(i);
for (int i=0; i<6; i++)add(i, i+1);
add(1, 4);
for (int i=0; i<7; i++)
for (int j=7; j<128; j++)
if(!(j&(1<<(6-i))))add(i, j);
}
void find7(){
for (int i=0; i<128; i++)
if(check(i))v.pb(i),f[i]=1;
for (int i=0; i<6; i++)
for (int j=i+1; j<7; j++){
g[i][j]=g[j][i]=check(v[i], v[j]);
sz[i]+=g[i][j];
sz[j]+=g[i][j];
}
for (int i=0; i<7; i++){
if(sz[i]>1)continue;
for (int j=0; j<7; j++){
if(!g[i][j] || sz[j]!=3)continue;
for (int k=0; k<7; k++)
if(g[j][k] && sz[k]==3)g[j][k]=g[k][j]=0;
V.pb(v[i]);
int x=i, pa=i, o=0;
while(!o){ o=1;
for (int k=0; k<7; k++)
if(g[x][k] && k!=pa)
V.pb(v[k]), o=0, pa=x, x=k;
}
}
}
for (int i=0; i<7; i++)Ans[V[i]]=i;
}
void solve(vector<int> p, int e=0, int x=1){
if(e==7 || p.size()==0)return;
int n=p.size(), T=(1<<(6-e)), k=0;
vector<int> L, R;
for (int i=0; i<n-1; i++)
if(check(V[e], p[i])) L.pb(p[i]), k++;
else Ans[p[i]]+=T, R.pb(p[i]);
if (k<A[x]) L.pb(p[n-1]);
else Ans[p[n-1]]+=T, R.pb(p[n-1]);
solve(L, e+1, x<<1);
solve(R, e+1, x<<1|1);
}
void findall(){
vector <int> p;
for (int i=0; i<128; i++)if(!f[i])p.pb(i);
solve(p);
}
vector<int> restore_permutation(int n, int w=0, int r=0){
for (int i=0; i<128; i++)s+='0';
buildA();
ADD();
compile_set();
find7();
findall();
return Ans;
}