Submission #1199114

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

messy

#include <bits/stdc++.h>
#include "messy.h"

using namespace std;
#define ll long long
#define REP(a,i,n) for (ll i=a;i<n;i++)

vector<int> sagot;

void adds(int n, int lo, int hi) {
    if (lo==hi) return;
    int mid = (lo+hi)/2;
    string s = string(n, '1');
    REP(lo, i, hi+1) s[i]='0';
    REP(lo, i, mid+1) {
        s[i]='1';
        add_element(s);
        s[i] = '0';
    }
    adds(n, lo, mid); adds(n, mid+1, hi);
}

void solve(int n, vector<int> can, int lo, int hi) {
    if (hi-lo==0) {
        sagot[lo] = can[0];
        return;
    }
    vector<int> left, right;
    string s = string(n, '1');
    for (auto u : can) {
        s[u] = '0';
    }
    for (auto u: can) {
        s[u]='1';
        if (check_element(s)) { 
            left.push_back(u);
        }
        else {
            right.push_back(u);
        }
        s[u]='0';
    }
    int mid = (lo+hi)/2;
    solve(n, left, lo, mid); solve(n, right, mid+1, hi);
}

vector<int> restore_permutation(int n, int w, int r) {
    sagot.resize(n);
    adds(n, 0, n-1);
    compile_set();
    vector<int> cans, ans(n);
    REP(0, i, n) {
        cans.push_back(i);
    }
    solve(n, cans, 0, n-1);
    REP(0, i, n) {
        ans[sagot[i]] = i;
    }
    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