oj.uz

Submission #247440

# Submission time Handle Problem Language Result Execution time Memory
247440 2020-07-11T11:52:57 Z kshitij_sodani Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 11 ms 640 KB 
#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

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.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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