Submission #1333383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1333383		a.pendov	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	2 ms	580 KiB

messy

#include <bits/stdc++.h>

#include "messy.h"
using namespace std;
long long N;
vector<int> ans;

void rec(int num,vector<int> pos,int log2)
{
    if(log2==-1)
    {
        ans[pos[0]]=num;
        return;
    }

    string str;
    for(int i=0; i<N; i++)str.push_back('1');
    for(auto i:pos)str[i]='0';

    vector<int> v0,v1;

    for(int i=0; i<N; i++)
    {
        if(str[i]=='0')
        {
            str[i]='1';
            if(check_element(str))
            {
                v1.push_back(i);
            }
            else
            {
                v0.push_back(i);
            }
            str[i]='0';
        }
    }

    rec(num,v0,log2-1);
    rec(num|(1LL<<log2),v1,log2-1);
}

std::vector<int> restore_permutation(int n, int w, int r)
{
    N=n;
    for(int i=0; i<N; i++)ans.push_back(0);
    int log2;
    switch(n)
    {
    case 8:
        log2=3;
        break;
    case 32:
        log2=5;
        break;
    case 128:
        log2=7;
        break;
    }

    for(int i=log2-1; i>=0; i--)
    {
        for(int j=0; j<n; j++)
        {
            if(j&(1LL<<i))
            {
                string str;
                for(int t=0; t<n; t++)
                {
                    if(t==j)
                    {
                        str.push_back('1');
                        continue;
                    }

                    str.push_back(bool((t^j)>=(1LL<<(i+1)))+'0');
                }

                add_element(str);
            }
        }
    }

    compile_set();

    vector<int> v;
    for(int i=0; i<n; i++)v.push_back(i);
    rec(0,v,log2-1);

    return ans;
}

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