Submission #1192709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192709		simona1230	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	2 ms	2888 KiB

messy

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

vector<int> v[100001];
int num;
vector<int> ans;
void rec(int i,int l,int r)
{
    /*cout<<i<<" "<<l<<" "<<r<<endl;
    for(auto j:v[i])
        cout<<j<<" ";
            cout<<endl;*/
    if(l==r)
    {
        ans[v[i][0]]=l;
        return;
    }
    string s="";
    for(int j=0;j<num;j++)
        s+='0';
    for(auto j:v[i])
        s[j]='1';

    int m=(l+r)/2;
    for(auto j:v[i])
    {
        s[j]='0';
        if(check_element(s))
            v[i*2].push_back(j);
        else v[i*2+1].push_back(j);
        s[j]='1';
    }

    rec(i*2,l,m);
    rec(i*2+1,m+1,r);
}

std::vector<int> restore_permutation(int n, int w, int r)
{
    num=n;
    int x=n;
    while(x!=1)
    {
        string s="";
        for(int i=0;i<n;i++)
            s+='0';

        for(int i=0;i<n;i+=x)
        {
            string s1=s;
            for(int j=0;j<x;j++)
                s1[i+j]='1';
            for(int j=0;j<x/2;j++)
            {
                s1[i+j]='0';
                //cout<<s1<<endl;
                add_element(s1);
                s1[i+j]='1';
            }
        }
        x/=2;
    }
    compile_set();
    for(int i=0;i<n;i++)
        ans.push_back(0),
        v[1].push_back(i);
    rec(1,0,n-1);

    return ans;
}

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