Submission #1227135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227135		Marco_Escandon	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	3 ms	1096 KiB

messy

#include "messy.h"
#include<bits/stdc++.h>
using namespace std;











#include<bits/stdc++.h>
using namespace std;
typedef int ll;
std::vector<int> restore_permutation(int n, int w, int r) {
    for(int i=0; i<log2(n); i++)
    {
        for(int j=0; j<n; j+=n/(1<<i))
        {
            string s;s.assign(n,'1');
            for(int k=0; k<n/(1<<i); k++)
            {
                s[j+k]='0';
            }
            for(int k=0; k<n/(2<<i); k++)
            {
                s[j+k]='1';
                add_element(s);
                //cerr<<s<<"\n";
                s[j+k]='0';
            }
        }
    }
    //cerr<<"\n\n";
    compile_set();
    vector<set<ll>> ans(n);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            ans[i].insert(j);
    for(int i=0; i<log2(n); i++)
    {
        for(int j=0; j<n; j+=n/(1<<i))
        {
            string s;s.assign(n,'1');
            for(auto k:ans[j])
            {
                s[k]='0';
            }
            set<ll> s2;
            for(int k=0;k<n;k++) s2.insert(k);
            //cerr<<s<<"---\n";
            for(auto k:ans[j])
            {
                s[k]='1';
                //cerr<<s<<"\n";
                if(check_element(s)) s2.erase(k);
                s[k]='0';
            }
            for(auto k:s2)
            {
                ans[j].erase(k);
            }
            for(int k=0; k<n/(2<<i); k++)
            {
                ans[j+k]=ans[j];
            }
            for(auto k:ans[j])
            {
                ans[j+n/(2<<i)].erase(k);
            }
            for(int k=n/(2<<i); k<n/(1<<i); k++)
            {
                ans[j+k]=ans[j+n/(2<<i)];
            }
        }
    }
    vector<ll> ans2(n);
    for(int i=0; i<n; i++)
    {
        ans2[*ans[i].begin()]=i;
    }
    
    return ans2;
}

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h: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