Submission #1095365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095365		idiotcomputer	Unscrambling a Messy Bug (IOI16_messy)	C++11	0 / 100	1 ms	604 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back

void cl(string &t){
	for (int i = 0; i < sz(t); i++) t[i] = '0';
}

bool chin(vector<int> &a, int v){
	for (int c : a) if (c == v) return 1;
	return 0;
}
vector<int> restore_permutation(int n, int w, int r){
	int k = 0;
	int c = 1;
	while (c < n){
		c *= 2;
		k++;
	}
	k = max(3,k);

	string t = "";
	for (int i = 0; i < n; i++) t += '0';
	for (int i = 0; i < k; i++){
		cl(t);
		t[i] = '1';
		add_element(t);
		for (int j = 0; j < i; j++) t[j] = '1';
		add_element(t);
	}
	cl(t);
	add_element(t);
	vector<pii> ranges;
	vector<pii> nex;
	ranges.pb((pii){k,n-1});
	int mid;
	for (int i = 0; i < k; i++){
		nex.clear();
		//cout << i << ": \n";
		for (pii c : ranges){
			if (c.f == c.s) continue;
			mid = (c.s + c.f)/2;
			nex.pb((pii) {c.f,mid});
			nex.pb((pii) {mid+1,c.s});
			//cout << c.f << " " << c.s << "\n";
			for (int j = mid+1; j <= c.s; j++){
				cl(t);
				t[j] = '1';
				for (int i2 = 0; i2 <= i; i2++) t[i2] = '1';
				add_element(t);
			}
		}
		swap(ranges,nex);
	}
	/*cout << k << "\n";
	for (string &c : all) cout << c << "\n";
	cout << "COMPILING:\n";*/
	compile_set();
	vector<int> ipos;
	for (int i = 0; i < n; i++){
		cl(t);
		t[i] = '1';
		if (check_element(t)) ipos.pb(i);
	}	
	/*for (int c : ipos) cout << c << ' ';
	cout << "\n";*/

	vector<int> ord;
	for (int i = 0; i < k; i++){
		for (int c : ipos){
			if (chin(ord,c)) continue;
			cl(t);
			for (int ct : ipos) t[ct] = '1';
			for (int ct : ord) t[ct] = '0';
			t[c] = '0';
			//if (i == 2) cout << c << " " << t << '\n';
			if (!check_element(t)) continue;
			ord.pb(c);
			break;
		}
	}
	/*for (int c : ord) cout << c << ' ';
	cout << "\n";*/
	for (int i = 0; i < k/2; i++) swap(ord[i],ord[k-i-1]);
	/*for (int c : ord) cout << c << ' ';
	cout << "\n";*/

	vector<int> res(n);
	pii range[n];
	for (int i = 0; i < n; i++) range[i] = {k,n-1};
	for (int i = 0; i < k; i++) range[ord[i]] = {i,i}; 
	for (int i = 0; i < k; i++){
		for (int j = 0; j < n; j++){
			if (range[i].f == range[i].s) continue;
 			cl(t);
			for (int i2 = 0; i2 <= i; i2++) t[ord[i2]] = '1';
			t[j] = '1';
			if (check_element(t)) range[i] = {(range[i].f+range[i].s)/2+1,range[i].s};
			else range[i] = {range[i].f, (range[i].f+range[i].s)/2};
		}
	}

	for (int i = 0; i < n; i++) res[i] = range[i].f;
	return res;
}

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