Submission #1160691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160691		DobromirAngelov	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	1 ms	584 KiB

messy

#include<bits/stdc++.h>
#include "messy.h"

using namespace std;

const int MAXN=128;

int n;
int ans[MAXN];

void getElements(int l,int r)
{
    if(l>=r) return;
    string  s="";
    s.resize(n,'1');

    for(int i=l;i<=r;i++) s[i]='0';
    int mid=(l+r)/2;
    for(int i=l;i<=mid;i++)
    {
        s[i]='1';
        add_element(s);
        s[i]='0';
    }

    getElements(l,mid);
    getElements(mid+1,r);
}

void solve(vector<int> cur,int bit)
{
    if(cur.size()==0 || bit<1) return;
    string s="";
    s.resize(n,'1');
    for(auto ind: cur) s[ind]='0';
    
    vector<int> l,r;
    for(auto ind: cur)
    {
        s[ind]='1';
        if(check_element(s)) l.push_back(ind);
        else 
        {
            r.push_back(ind);
            ans[ind]|=bit;
        }
        s[ind]='0';
    }

    solve(l,bit/2);
    solve(r,bit/2);
}

std::vector<int> restore_permutation(int _n, int w, int r)
{
    n=_n;

    getElements(0,n-1);
    compile_set();

    vector<int> tmp;
    for(int i=0;i<n;i++) tmp.push_back(i);
    int bit=1;
    while(bit<n/2) bit*=2;
    solve(tmp,bit);

    vector<int> ret;
    ret.resize(n);
    for(int i=0;i<n;i++) ret[i]=ans[i];
    return ret;
}

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