Submission #1146597

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

messy

#include <vector>
#include<iostream>
#include<algorithm>
#include<string>
#include "messy.h"
using namespace std;
namespace{
    string templ, temp1;
    vector<int> ans;
    void encode(int l, int r, int n){
        if(l == r) return;
        string s = templ;
        for(int i = 0; i < l; i++) s[i] = '1';
        for(int i = r + 1; i < n; i++) s[i] = '1';
        int mid = (l + r) >> 1;
        for(int i = l; i <= mid; i++){
            s[i] = '1';
            add_element(s);
            s[i] = '0';
        } 
        encode(l, mid, n);
        encode(mid + 1, r, n);
    }
    void decode(int l, int r, vector<int> cur){
        if(l == r){
            ans[cur[0]] = l;
            return;
        }
        int mid = (l + r) >> 1;
        vector<int> lc, rc;
        string s = temp1;
        for(auto x: cur) s[x] = '0';
        for(auto x: cur){
            s[x] = '1';
            if(check_element(s)) lc.push_back(x);
            else rc.push_back(x);
            s[x] = '0';
        }
        decode(l, mid, lc);
        decode(mid + 1, r, rc);
    }
}

std::vector<int> restore_permutation(int n, int w, int r) {
    templ = string(n, '0');
    temp1 = string(n, '1');
    ans.resize(n);
    encode(0, n - 1, n);
    compile_set();
    vector<int> vec(n);
    for(int i = 0; i < n; i++) vec[i] = i;
    decode(0, n - 1, vec);
    return ans;
}
// g++ -std=c++20 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp messy.cpp

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