Submission #1150355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150355		LCJLY	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	2 ms	584 KiB

messy

#include "messy.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

//add_element("0100101")
//compile_set()
//check_element("01001011")


vector<int>restore_permutation(int n, int w, int r) {
    int arr[n][7];
    for(int x=0;x<n;x++){
		for(int y=0;y<7;y++){
			if(x&(1<<y)){
				arr[x][y]=1;
			}
			else arr[x][y]=0;
		}
	}
	
	//layer 1
	for(int x=1;x<n;x+=2){
		string s="";
		for(int y=0;y<n;y++) s+="0";
		string s2=s;
		s2[x]='1';
		add_element(s2);
	}
	
	int take=0;
	int cur=n;
	while(cur>1){
		cur/=2;
		take++;
	}
	
	//layer 2 and above
	for(int bit=1;bit<take;bit++){
		//ones
		string s="";
		for(int x=0;x<n;x++){
			if(arr[x][bit-1]==1) s+="1";
			else s+="0";
		}
		
		for(int x=0;x<n;x++){
			if(arr[x][bit]==1&&arr[x][bit-1]==1){
				string s2=s;
				s2[x]='0';
				add_element(s2);
			}
			else if(arr[x][bit]==0&&arr[x][bit-1]==0){
				string s2=s;
				s2[x]='1';
				add_element(s2);
			}	
		}
	}
	
	compile_set();
	
	int ans[n][7];
	memset(ans,0,sizeof(ans));
	
	//layer 1 
	for(int x=0;x<n;x++){
		string s="";
		for(int y=0;y<n;y++) s+="0";
		s[x]='1';
		ans[x][0]=check_element(s);
	}
	
	//layer 2 and above
	for(int bit=1;bit<take;bit++){
		string s="";
		for(int x=0;x<n;x++){
			if(ans[x][bit-1]==1) s+="1";
			else s+="0";
		}

		for(int x=0;x<n;x++){
			if(ans[x][bit-1]==1){
				//one
				string s2=s;
				s2[x]='0';
				ans[x][bit]=check_element(s2);
			}
			else{
				//zero
				string s2=s;
				s2[x]='1';
				ans[x][bit]=!check_element(s2);
			}
		}
	}

	vector<int>cnt(n,0);
	for(int x=0;x<n;x++){
		for(int y=0;y<take;y++){
			cnt[x]+=(ans[x][y]<<y);
		}
	}
	
	return cnt;
}

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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