Submission #1095374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095374		idiotcomputer	Unscrambling a Messy Bug (IOI16_messy)	C++11	100 / 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
#include <random>
 
 
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;
	//cout << c2 << '\n';
	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";
	//cout << k << " " << c2 << '\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;
		}
	}
	//cout << c2 << '\n';
	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;}
	}
	//cout << c2 << '\n';
	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";*/
	//cout << k << " " << c2 << '\n';
	vector<int> res(n);
	bool vis[n];
	memset(vis,0,sizeof(vis));
	//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 < n; i++){
		if (chin(ord,i)) continue;
		pii cur = {k,n-1};
		int ck = 0;
		while (1){
			int cnt = -1;
			for (int j = cur.f; j <= cur.s; j++){
				if (vis[j]) continue;
				if (cnt != -1){ cnt = -2; break;}
				cnt = j;
			}
			if (cnt > -1){
				res[i] = cnt;
				vis[cnt] = 1;
				break;
			}
			cl(t);
			for (int j = 0; j <= ck; j++) t[ord[j]] = '1';
			t[i] = '1';
			if (check_element(t)) cur = {(cur.f+cur.s)/2+1, cur.s};
			else cur = {cur.f, (cur.f+cur.s)/2};
			ck++;
		}
	}
	for (int i = 0; i < k; i++) res[ord[i]] = i;
	//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: 30 / 30