Submission #1095369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095369		idiotcomputer	Unscrambling a Messy Bug (IOI16_messy)	C++11	70 / 100	2 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(4,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);
	t[0] = '1';
	t[k-1] = '1';
	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-2; 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);
			if (i == 0 && c == 0) cout <<"IN "<< t << '\n';
			break;
		}
	}
	for (int c : ipos){
		if (chin(ord,c)) continue;
		cl(t);
		t[c] = '1';
		t[ord[0]] = '1';
		if (!check_element(t)){ ord.pb(c); break;}
	}
	for (int c : ipos) if (!chin(ord,c)){ 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}; 
	//cout << k << " " << n << '\n';
	for (int i = 0; i < k; i++){
		for (int j = 0; j < n; j++){
			//cout << j << " - " << range[j].f << "," << range[j].s << '\n';
			if (range[j].f == range[j].s) continue;
 			cl(t);
			for (int i2 = 0; i2 <= i; i2++) t[ord[i2]] = '1';
			t[j] = '1';
			//cout << i << "-" << j <<" " << t << '\n';
			if (check_element(t)) range[j] = {(range[j].f+range[j].s)/2+1,range[j].s};
			else range[j] = {range[j].f, (range[j].f+range[j].s)/2};
		}
	}

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

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