Submission #144038

#	Time	Username	Problem	Language	Result	Execution time	Memory
144038		dorijanlendvaj	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	6 ms	504 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);
    		}
    		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;
    		}
    		a=c;
    	}
    	vi bio(n);
    	for (auto a: ans) ++bio[a];
    	int z=0;
    	for (auto a: bio) z+=abs(a-1);
    	return ans;
    }

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