Submission #1204329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204329		Aviansh	Unscrambling a Messy Bug (IOI16_messy)	C++20	49 / 100	1 ms	328 KiB

messy

#include "messy.h"

#include <bits/stdc++.h>

using namespace std;

vector<int> restore_permutation(int n, int w, int r) {
    srand(2357);
    string curr = "";
    for(int i = 0;i<n;i++){
        curr+="0";
    }
    for(int i = 0;i<n-1;i++){
        curr[i]='1';
        add_element(curr);
    }
    vector<int>ans(n);
    compile_set();
    for(int i = 0;i<n;i++){
        curr[i]='0';
    }
    vector<int>pos(n);
    iota(pos.begin(),pos.end(),0);
    for(int i = 1;i<n;i++){
        //attempting to find where first 1 went
        vector<int>cur=pos;
        int fin = -1;
        while(1){
            int ind = rand() % cur.size();
            curr[cur[ind]]='1';
            if(check_element(curr)){
                fin=cur[ind];
                break;
            }
            curr[cur[ind]]='0';
            swap(cur[ind],cur[cur.size()-1]);
            cur.pop_back();
        }
        assert(fin!=-1);
        int fini = -1;
        for(int i = 0;i<pos.size();i++){
            if(pos[i]==fin){
                fini=i;
                break;
            }
        }
        swap(pos[fini],pos[pos.size()-1]);
        pos.pop_back();
        //discovered new character
        //i-1th bit went to fin
        ans[fin]=i-1;
    }
    ans[pos[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: 0 / 21
• Subtask 5: 0 / 30