Submission #241787

#	Time	Username	Problem	Language	Result	Execution time	Memory
241787		crossing0ver	Unscrambling a Messy Bug (IOI16_messy)	C++17	0 / 100	2094 ms	512 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
int X[500],L[500],R[500],IN[500];
vector<int> perm;
map<string,bool> mp;
/*void add_element(string s) {
	mp[s] = 1;
}
void compile_set() {
	for (int i = 0; i < perm.size(); i++) perm[i] = i;
	random_shuffle(perm.begin(),perm.end());
}
bool check_element(string s) {
	return mp[s];
}*/
vector<int> restore_permutation(int n, int w, int r) {
  srand(time(NULL));
	int lg = log2(n);
	perm.resize(n);
	int l = -1;
	string s(n,'0');
	for (int val = n/2;val;val/=2) {
		for (int i = l+1; i < n; i++) {
			if ( (i & ( val) ) == 0)	{
				s[i] = '1';
				add_element(s);
				cout << s <<'\n';
				s[i] = '0';
			}
		}
		s[++l] = '1';
	}
    compile_set();
    for (int i = 0;i < n; i++) s[i] = '0';
    vector<int> st;
    vector<int> not1;
    for (int i = 0; i < n; i++) not1.push_back(i);
    int val = n/2;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j*=2) X[i]^=j;
    while (val) {
    	vector<int> v;
    for (int i = 0; i < n; i++) {
    	if (IN[i]) continue;
    	s[i] = '1';
    	if ( check_element(s)){
    		v.push_back(i);
    		X[i]^=val;
		}	
    	s[i] = '0';
	}
	cnt++;
	vector<bool> vis(n+1);
	while (not1.size() > 1) {
      bool flag = 0;
		int pos = rand()%not1.size();
		for (int i : v) {
			int t = 5;
			int g = 0;
          while(t--) {
            
			int pos = rand()%not1.size();
			s[not1[pos]] ='1';
			s[i]   = '1';
			if (check_element(s)) {
              g++;
			}
			if (g >= 2){
				flag = 1;
				s[i] = '1';
				IN[i] = 1;
				not1.erase(find(not1.begin(),not1.end(),i));
			}
            s[not1[pos]] = '0';
            if (flag) break;
            s[i] = '0';
          }
          if (flag) break;
		}
	if (flag) break;
	}
      val/=2;
	}
	vector<int> ans;
   for (int i = 0;i < n; i++)
   		ans.push_back(X[i]);
   	return ans;
   	
}

Compilation message (stderr)

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:58:7: warning: unused variable 'pos' [-Wunused-variable]
   int pos = rand()%not1.size();
       ^~~
messy.cpp:19:6: warning: unused variable 'lg' [-Wunused-variable]
  int lg = log2(n);
      ^~

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