Submission #1020868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020868		pawned	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	4 ms	860 KiB

messy

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "messy.h"

int lg(int N) {
	int curr = 1;
	int res = 0;
	while (curr < N) {
		curr *= 2;
		res++;
	}
	return res;
}

string sor(string x, string y) {	// XOR of strings w/ same length
	int M = x.size();
	string res;
	for (int i = 0; i < M; i++) {
		if (x[i] == y[i])
			res += '0';
		else
			res += '1';
	}
	return res;
}

vi restore_permutation(int N, int W, int R) {
	int M = lg(N);	// power of 2
	vector<string> bases(M, string((1 << M), '0'));
	for (int i = 1; i < M - 1; i++) {
		int upto = (1 << M) - (1 << (M - i)) - 1;
//		cout<<i<<": "<<upto<<endl;
		for (int j = 0; j <= upto; j++) {
			bases[i][j] = '1';
		}
	}
	bases[M - 1] = string((1 << M), '1');
/*	cout<<"bases: ";
	for (string s : bases)
		cout<<s<<" ";
	cout<<endl;*/
	// get what all ith bit off maps to, then each appears in exactly one
	// the val it maps to appears exactly in those where its bit is off
	vector<string> tq;	// to query
	for (int i = M - 1; i >= 0; i--) {
		vector<string> ctq;	// to query for set i
		for (int j = 0; j < (1 << M); j++) {
			if ((j & (1 << i)) == 0) {
				string rt((1 << M), '0');
				rt[j] = '1';
				ctq.pb(sor(rt, bases[M - i - 1]));
			}
		}
/*		cout<<i<<": ";
		for (string s : ctq)
			cout<<s<<" ";
		cout<<endl;*/

		for (string s : ctq)
			tq.pb(s);
	}
	for (string s : tq)
		add_element(s);
	compile_set();
	vector<vector<bool>> aft(M, vector<bool>((1 << M), false));
	// what set i becomes after perm
	// set i: all of bit (M - i - 1) are off
	string currb((1 << M), '0');
	for (int i = 0; i < M; i++) {
//		cout<<"at "<<i<<endl;
		if (i == M - 1)
			currb = string((1 << M), '1');
		vi bec;
		for (int j = 0; j < (1 << M); j++) {
			string rt((1 << M), '0');
			rt[j] = '1';
			string qr = sor(rt, currb);
//			cout<<"asking "<<qr<<endl;
			bool res = check_element(qr);
			if (res) {
//				cout<<"orz"<<endl;
				bec.pb(j);
				aft[i][j] = true;
			}
		}
		// bec has size (1 << (M - 1))
		for (int x : bec)
			currb[x] = '1';

	}
/*	cout<<"aft: "<<endl;
	for (int i = 0; i < M; i++) {
		cout<<"set "<<i<<": ";
		for (int j = 0; j < (1 << M); j++) {
			if (aft[i][j])
				cout<<1<<" ";
			else
				cout<<0<<" ";
		}
		cout<<endl;
	}*/
	vi ans((1 << M), -1);
	for (int i = 0; i < (1 << M); i++) {
		for (int j = 0; j < (1 << M); j++) {
			bool same = true;
			// check if sets of j completely match i's
			for (int k = 0; k < M; k++) {
				if (aft[M - 1 - k][j] && ((i & (1 << k)) != 0))
					same = false;
				if (!aft[M - 1 - k][j] && ((i & (1 << k)) == 0))
					same = false;
			}
			if (same) {
				ans[j] = i;
			}
		}
	}
/*	cout<<"ANSWER: ";
	for (int x : ans)
		cout<<x<<" ";
	cout<<endl;*/
	return ans;
}

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