Submission #119124

#	Time	Username	Problem	Language	Result	Execution time	Memory
119124		dorijanlendvaj	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	512 KiB

messy

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
using namespace std;
#define x first
#define y second
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
const char en='\n';
#include "messy.h"


void flip(string&a,int i)
{
	a[i]='0'+'1'-a[i];
}

bool debug=0;
int rr,ww;

void add(string b)
{
	++ww;
	add_element(b);
	if (debug) cout<<"added "<<b<<endl;
}

bool check(string b,int r)
{
	++rr;
	flip(b,r);
	bool x=check_element(b);
	flip(b,r);
	return x;
}

vi restore_permutation(int n, int w, int r) {
	//assert(n==8);
	string b;
	for (int i=0;i<n;++i) b.pb('0');
	mt19937 rng1(1),rng2(1);
    for (int i=1;i<n;i*=2)
    {
    	string c=b;
    	for (int j=0;j<n;++j) if (j&i)
    	{
    		flip(b,j);
    		flip(c,j);
    		add(b);
    		flip(b,j);
		}
		int z=rng1();
		if (z%2)
		{
			for (int j=0;j<n;++j) flip(c,j);
		}
		b=c;
	}
	compile_set();
	string a;
	for (int i=0;i<n;++i) a.pb('0');
	vi ans(n);
	for (int i=0;(1<<i)<n;++i)
	{
		if (debug) cout<<"a is "<<a<<endl;
		string c=a;
		for (int j=0;j<n;++j) if (check(a,j))
		{
			flip(c,j);
			ans[j]+=1<<i;
		}
		int z=rng2();
		if (z%2)
		{
			for (int j=0;j<n;++j) flip(c,j);
		}
		a=c;
	}
	vi bio(n);
	for (auto a: ans) ++bio[a];
	int z=0;
	for (auto a: bio) z+=abs(a-1);
	//assert(z<=2);
	return ans;
}

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