oj.uz

Submission #54925

# Submission time Handle Problem Language Result Execution time Memory
54925 2018-07-05T12:43:16 Z WA_TLE Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 5 ms 512 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 8
2 Correct 2 ms 384 KB n = 8
3 Correct 2 ms 256 KB n = 8
4 Correct 2 ms 384 KB n = 8
5 Correct 2 ms 256 KB n = 8
6 Correct 2 ms 256 KB n = 8
7 Correct 2 ms 256 KB n = 8
8 Correct 2 ms 384 KB n = 8
9 Correct 2 ms 384 KB n = 8
10 Correct 2 ms 256 KB n = 8
11 Correct 2 ms 384 KB n = 8
12 Correct 2 ms 256 KB n = 8
13 Correct 2 ms 256 KB n = 8
14 Correct 2 ms 256 KB n = 8
15 Correct 2 ms 256 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 32
2 Correct 2 ms 384 KB n = 32
3 Correct 2 ms 384 KB n = 32
4 Correct 2 ms 384 KB n = 32
5 Correct 2 ms 384 KB n = 32
6 Correct 3 ms 384 KB n = 32
7 Correct 2 ms 384 KB n = 32
8 Correct 2 ms 384 KB n = 32
9 Correct 2 ms 384 KB n = 32
10 Correct 2 ms 384 KB n = 32
11 Correct 2 ms 384 KB n = 32
12 Correct 2 ms 384 KB n = 32
13 Correct 2 ms 384 KB n = 32
14 Correct 2 ms 384 KB n = 32
15 Correct 2 ms 384 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 32
2 Correct 2 ms 384 KB n = 32
3 Correct 3 ms 384 KB n = 32
4 Correct 2 ms 384 KB n = 32
5 Correct 2 ms 384 KB n = 32
6 Correct 2 ms 384 KB n = 32
7 Correct 2 ms 384 KB n = 32
8 Correct 3 ms 384 KB n = 32
9 Correct 2 ms 384 KB n = 32
10 Correct 2 ms 384 KB n = 32
11 Correct 2 ms 384 KB n = 32
12 Correct 2 ms 384 KB n = 32
13 Correct 2 ms 384 KB n = 32
14 Correct 2 ms 384 KB n = 32
15 Correct 2 ms 384 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB n = 128
2 Correct 5 ms 512 KB n = 128
3 Correct 5 ms 512 KB n = 128
4 Correct 5 ms 512 KB n = 128
5 Correct 4 ms 488 KB n = 128
6 Correct 5 ms 512 KB n = 128
7 Correct 4 ms 512 KB n = 128
8 Correct 4 ms 512 KB n = 128
9 Correct 5 ms 512 KB n = 128
10 Correct 4 ms 512 KB n = 128
11 Correct 4 ms 512 KB n = 128
12 Correct 4 ms 512 KB n = 128
13 Correct 5 ms 512 KB n = 128
14 Correct 5 ms 512 KB n = 128
15 Correct 5 ms 512 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB n = 128
2 Correct 5 ms 512 KB n = 128
3 Correct 5 ms 512 KB n = 128
4 Correct 4 ms 512 KB n = 128
5 Correct 5 ms 512 KB n = 128
6 Correct 5 ms 512 KB n = 128
7 Correct 5 ms 512 KB n = 128
8 Correct 4 ms 512 KB n = 128
9 Correct 5 ms 512 KB n = 128
10 Correct 5 ms 512 KB n = 128
11 Correct 5 ms 512 KB n = 128
12 Correct 4 ms 512 KB n = 128
13 Correct 4 ms 512 KB n = 128
14 Correct 5 ms 512 KB n = 128
15 Correct 4 ms 512 KB n = 128