Submission #247440

#	Time	Username	Problem	Language	Result	Execution time	Memory
247440		kshitij_sodani	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	11 ms	640 KiB

messy

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
mt19937 rng;
void add_element(string x);
bool check_element(string x);
void compile_set();
//#include "messy.h"
vector<int> ans;
int nn;
void divide(set<int> cur,int ind,int stop,int num){
	if(ind==stop){
		ans[*(cur.begin())]=num;//*(cur.begin());
		return;
	}

	set<int> cur2;
	set<int> cur3;
	for(auto j:cur){
		string s="";
		for(int k=0;k<nn;k++){
			if(k==j){
				s+="1";
			}
			else if(cur.find(k)==cur.end()){
				s+="1";
			}
			else{
				s+="0";
			}
		}
	//	cout<<s<<":"<<endl;

		if(check_element(s)){
			cur2.insert(j);
		}
		else{
			cur3.insert(j);
		}
	}
	divide(cur2,ind+1,stop,num+(1<<ind));
	divide(cur3,ind+1,stop,num);
}
std::vector<int> restore_permutation(int n, int w, int r) {
	nn=n;
 	int x=3;
 	for(int i=0;i<n;i++){
 		ans.pb(0);
 	}
 	if(n==32){
 		x=5;
 	}
 	if(n==128){
 		x=7;
 	}
 	if(n==4){
 		x=2;
 	}
 	int val[n];
 	for(int i=0;i<n;i++){
 		val[i]=0;
 	}
 	for(int i=0;i<x;i++){
 		for(int j=0;j<n;j++){
 			
 			if((j&(1<<i))){
 				int xx=(1<<i)-1;
 				string s="";
 				for(int k=0;k<n;k++){
 					if(k==j){
 						s+="1";
 					}
 					else if(val[k]!=val[j]){
 						s+="1";
 					}
 					else{
 						s+="0";
 					}
 				}
 				add_element(s);
 			//	cout<<s<<endl;
 			}
 		}
 		for(int j=0;j<n;j++){
 			val[j]+=(j&(1<<i));
 		}
 	}
 	compile_set();
 	set<int> cur;
 	for(int i=0;i<n;i++){
 		cur.insert(i);
 	}
 	divide(cur,0,x,0);

  //  check_element("0");
    return ans;
}

/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);



	return 0;
}
*/
/*
g++  -o aa -O2 messy.cpp grader.cpp -std=c++14

*/
/*
4 16 16
2 1 3 0
*/

Compilation message (stderr)

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:72:10: warning: unused variable 'xx' [-Wunused-variable]
      int xx=(1<<i)-1;
          ^~

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