Submission #54925

#	Time	Username	Problem	Language	Result	Execution time	Memory
54925		WA_TLE	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	5 ms	512 KiB

messy

#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;}}
#include"messy.h"
/*
びっとをうまく使う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;
}

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30