Submission #1034755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034755		lucri	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	2 ms	860 KiB

messy

#pragma once

#include <vector>
#include <string>

void add_element(std::string x);
bool check_element(std::string x);
void compile_set();
std::vector<std::vector<int>>ans;
bool aflat[130],e[130];
std::vector<int> restore_permutation(int n, int w, int r)
{
    std::string s;
    for(int i=1;i<=n;++i)
        s+='0';
    int p2=n/2,st=0,gr;
    while(p2)
    {
        for(int b=0;b<p2;++b)
        {
            s[st+b]='1';
            add_element(s);
            s[st+b]='0';
        }
        for(int b=0;b<p2;++b)
            s[st+b]='1';
        st+=p2;
        p2/=2;
    }
    p2=1;
    for(int i=0;i<n;++i)
        s[i]='0';
    for(int i=n/4;i>=1;i/=2)
    {
        p2*=2;
        for(int j=p2/2+1;j<=p2;++j)
            s[n-j]='1';
        st=0;
        gr=n/2;
        int valac=i;
        for(int nr=i;nr>=1;nr/=2)
        {
            for(int j=0;j<gr;++j)
                if((j/valac)%2==0)
                {
                    s[st+j]='1';
                    add_element(s);
                    s[st+j]='0';
                }
            st+=gr;
            gr/=2;
            valac/=2;
        }
    }
    compile_set();
    ans.resize(n*n);
    for(int i=0;i<n;++i)
        s[i]='0';
    gr=n/2;
    st=0;
    for(;gr>=1;gr/=2)
    {
        for(int i=0;i<n;++i)
        {
            if(e[i]==false&&aflat[i]==false)
            {
                s[i]='1';
                if(check_element(s))
                {
                    e[i]=true;
                    ans[st*n+(st+gr-1)].push_back(i);
                }
                s[i]='0';
            }
        }
        st+=gr;
        for(int i=0;i<n;++i)
            if(e[i]==true)
                s[i]='1';
    }
    for(int i=0;i<n;++i)
        if(e[i]==false)
            ans[(n-1)*n+n-1].push_back(i);
    for(int i=0;i<n;++i)
        s[i]='0';
    p2=1;
    aflat[ans[(n-1)*n+n-1][0]]=true;
    while(p2<n/2)
    {
        p2*=2;
        for(auto x:ans[(n-p2)*n+n-(p2/2+1)])
        {
            aflat[x]=true;
            s[x]='1';
        }
        for(int i=0;i<n;++i)
            e[i]=false;
        for(int i=0;i<n;++i)
        {
            if(e[i]==false&&aflat[i]==false)
            {
                s[i]='1';
                if(check_element(s))
                {
                    e[i]=true;
                    ans[st*n+(st+gr-1)].push_back(i);
                }
                s[i]='0';
            }
        }
        st=0;
        gr=n/2;
        while(1)
        {
            while(gr!=1&&ans[st*n+(st+gr/2-1)].size())
                gr/=2;
            if(gr==1)
                break;
            for(auto x:ans[st*n+st+gr-1])
            {
                if(e[x])
                    ans[st*n+st+gr/2-1].push_back(x);
                else
                    ans[(st+gr/2)*n+st+gr-1].push_back(x);
            }
            st+=gr;
        }
    }
    std::vector<int>ansf;
    ansf.resize(n);
    for(int i=0;i<n;++i)
        ansf[ans[i*n+i][0]]=i;
    return ansf;
}

Compilation message (stderr)

messy.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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