Submission #1272121

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

messy

#include "messy.h"

#include <bits/stdc++.h>

using namespace std;

int N;

void build(int l, int r){
    if(l==r){
        return;
    }
    int mid = (l+r)/2;
    string s = "";
    for(int i = 0;i<N;i++){
        s+="1";
    }
    for(int i = l;i<=r;i++){
        s[i]='0';
    }
    for(int i = l;i<=mid;i++){
        s[i]='1';
        add_element(s);
        s[i]='0';
    }
    build(l,mid);
    build(mid+1,r);
}

vector<int>ans;

void check(int l, int r, vector<int>inds){
    assert(r-l+1==inds.size());
    if(l==r){
        ans[inds[0]]=l;
        return;
    }
    string s = "";
    for(int i = 0;i<N;i++){
        s+="1";
    }
    for(int i : inds){
        s[i]='0';
    }
    vector<int>lef;
    vector<int>rig;
    for(int i = 0;i<inds.size();i++){
        s[inds[i]]='1';
        if(check_element(s)){
            lef.push_back(inds[i]);
        }
        else{
            rig.push_back(inds[i]);
        }
        s[inds[i]]='0';
    }
    int mid = (l+r)/2;
    check(l,mid,lef);
    check(mid+1,r,rig);
}

vector<int> restore_permutation(int n, int w, int r) {
    N=n;
    build(0,n-1);
    compile_set();
    ans=vector<int>(n);
    vector<int>inds(n);
    iota(inds.begin(),inds.end(),0);
    check(0,n-1,inds);
    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