| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 54924 | WA_TLE | Unscrambling a Messy Bug (IOI16_messy) | C++14 | 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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1e9+7;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
/*
びっとをうまく使う128
128 発見(3bit) 1000...
01111111
00111111(反転)
特定
125*7 特定
これをうまくやる必要がありそう
writeは大丈夫
一応pがランダムでないとき対策にこっちもrandかける
*/
vector<int>nara;
int N;
void add(string in){
string x(N,'x');
for(int i=0;i<N;i++){x[i]=in[nara[i]];}
add_element(x);
}
bool chehe(string in){
string x(N,'x');
for(int i=0;i<N;i++){x[i]=in[nara[i]];}
return check_element(x);
}
std::vector<int> restore_permutation(int nn, int w, int r) {
//順列をどうにかする
N=nn;
nara.res(N);
int i,j,k;
for(i=0;i<N;i++){nara[i]=i;}
mt19937 engine(1333);
shuffle(nara.begin(),nara.end(),engine);
vector<int>ans(N,-1);
int bn=1;
while((1<<bn)<N){bn++;}
//まず最初の3bitを生成する
string in(N,'0');
in[0]='1';add(in);in[0]='0';
in[1]='1';add(in);in[1]='0';
in[2]='1';add(in);in[2]='0';
for(i=0;i<N;i++){in[i]='1';}
in[0]='0';add(in);
in[1]='0';add(in);
for(i=0;i<N;i++){in[i]='0';}
//次に残りのbitを生成する
for(i=3;i<N;i++){
in[i]='1';
for(j=0;j<bn;j++){
if((i&(1<<j))==0){continue;}
for(k=0;k<3;k++){if((j+1)&(1<<k)){in[k]='1';}}
add(in);
for(k=0;k<3;k++){if((j+1)&(1<<k)){in[k]='0';}}
}
in[i]='0';
}
compile_set();
//まず0～2bitを探す
vector<int>go;
for(i=0;i<N;i++){
in[i]='1';
if(chehe(in)){go.pub(i);}
in[i]='0';
if(go.size()>=3){break;}
}
bool che=false;
for(i=0;i<N;i++){in[i]='1';}
in[go[2]]='0';
che=chehe(in);
in[go[2]]='1';
if(che){swap(go[2],go[0]);}
else{
in[go[1]]='0';
che=chehe(in);
in[go[1]]='1';
if(che){swap(go[1],go[0]);}
}
in[go[0]]='0';
in[go[2]]='0';
if(chehe(in)){swap(go[2],go[1]);}
for(i=0;i<N;i++){in[i]='0';}
//逆のやつで判定した
ans[go[0]]=0;
ans[go[1]]=1;
ans[go[2]]=2;
//のこりのbitを求める
for(i=0;i<N;i++){
if(ans[i]>=0){continue;}
in[i]='1';
//直接3～Nが入る
//なるべく半半に割れるようなbitを選ぶ
vector<bool>ari(N,1);
for(j=0;j<N;j++){if(ans[j]>=0){ari[ans[j]]=0;}}
while(-1){
int ware=1333;int sor=-1;
int zen=0;
for(k=0;k<N;k++){if(ari[k]){zen++;}}
if(zen==1){break;}
for(j=0;j<bn;j++){
int now=0;
for(k=0;k<N;k++){if(ari[k]&&((1<<j)&k)){now++;}}
maxeq(now,zen-now);
if(ware>now){ware=now;sor=j;}
}
//sorで分ける
for(k=0;k<3;k++){if((sor+1)&(1<<k)){in[go[k]]='1';}}
bool ch=chehe(in);
for(k=0;k<3;k++){if((sor+1)&(1<<k)){in[go[k]]='0';}}
if(ch){for(k=0;k<N;k++){if(!((1<<sor)&k)){ari[k]=0;}}}
else {for(k=0;k<N;k++){if( ((1<<sor)&k)){ari[k]=0;}}}
}
for(k=0;k<N;k++){if(ari[k]){ans[i]=k;break;}}
in[i]='0';
}
vector<int>ret(N);
vector<int>gara(N);
for(i=0;i<N;i++){gara[nara[i]]=i;}
for(i=0;i<N;i++){ret[i]=gara[ans[nara[i]]];}
return ret;
}