Submission #1184661

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

messy

#include <vector>
#include <iostream>
#include <algorithm>
#include "messy.h"
using namespace std;

string cur;
vector<string> added;
vector<int> ans, pos;

void recur_add(int l, int r) {
    int mid = (l+r) >> 1;
    for(int i=l;i<=r;i++) {
        cur[i] = '0';
    }
    for(int i=l;i<=mid;i++) {
        cur[i] = '1';
        add_element(cur);
        added.push_back(cur);
        cur[i] = '0';
    }
    for(int i=l;i<=mid;i++) cur[i] = '1';
    if(l != r && ((l+1!=r))) recur_add(mid+1, r);
    for(int i=mid+1;i<=r;i++) {
        cur[i] = '0';
    }
    if(l+1 != r) cur[r] = '1';
    if(l != r && (l+1 != r)) recur_add(l, mid);
}

void recur_ans(int l, int r, vector<int> candidates) {
    int mid = (l+r) >> 1;
    for(int &e:candidates) cur[e] = '0';
    vector<int> yeshaha, noawww;
    for(int &e:candidates) {
        cur[e] = '1';
        if(check_element(cur)) {
            yeshaha.push_back(e);
        } else {
            noawww.push_back(e);
        }
        cur[e] = '0';
    }
    if(l+1 == r) {
        //special case, do some magical shit??
        ans[l] = yeshaha[0];
        ans[l+1] = noawww[0];
        return;
    }

    for(int &e:yeshaha) cur[e] = '1';
    recur_ans(mid+1, r, noawww);
    for(int &e:noawww) cur[e] = '0';
    cur[ans[r]] = '1';
    recur_ans(l, mid, yeshaha);
}

std::vector<int> restore_permutation(int n, int w, int r) {
    cur = string(n, '0');
    recur_add(0, n-1);
    //for(auto &e:added) cout << e << " -> " << count(e.begin(), e.end(), '1') << '\n';
    compile_set();
    ans.resize(n);
    cur = string(n, '0');
    vector<int> cands;
    for(int i=0;i<n;i++) cands.push_back(i);
    recur_ans(0, n-1, cands);
    pos.resize(n);
    for(int i=0;i<n;i++) pos[ans[i]] = i;
    //for(int &e:pos) cout << e << ' ';
    return pos;
}

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