Submission #1205885

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

messy

#include <vector>

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

void add(int n, string pre, string suf){
    if(n==1){
        return;
    }
    string s="",tmp="";
    for(int i=0;i<n;i++){
        s+='0';
    }
    for(int i=0;i<n/2;i++){
        s[i]='1';
        add_element(pre+s+suf);
        s[i]='0';
    }
    for(int i=0;i<n/2;i++){
        tmp+='1';
    }
    add(n/2,pre+tmp,suf);
    add(n/2,pre,tmp+suf);
}

vector<int> solve(int n, string cur, int l, int r, vector<int> pos){
    if(r==l){
        return {pos[0]};
    }
    vector<int> l_pos,r_pos;
    string l_cur=cur,r_cur=cur;
    for(int i=0;i<n;i++){
        cur[pos[i]]='1';
        if(check_element(cur)){
            l_cur[pos[i]]='1';
            l_pos.push_back(pos[i]);
        }else{
            r_cur[pos[i]]='1';
            r_pos.push_back(pos[i]);
        }
        cur[pos[i]]='0';
    }
    vector<int> ans1=solve(n/2,r_cur,l,r-n/2,l_pos),ans2=solve(n/2,l_cur,l+n/2,r,r_pos);
    for(auto u:ans2){
        ans1.push_back(u);
    }
    return ans1;
}

std::vector<int> restore_permutation(int n, int w, int r) {
    int cnt;
    string s="",tmp;
    vector<int> ans,real(n);
    for(int i=0;i<n;i++){
        s+='0';
        ans.push_back(i);
    }
    add(n,"","");
    compile_set();
    ans=solve(n,s,0,n-1,ans);
    for(int i=0;i<n;i++){
        real[ans[i]]=i;
    }
    return real;
}

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