Submission #1233300

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

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;

vector<int> ans;
int n;

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

void query(int l, int r, vector<int> &indices)
{
    if (l == r - 1)
    {
        ans[indices[0]] = l;
        return;
    }
    string str(n, '0');
    for (auto idx : indices)
        str[idx] = '1';
    vector<int> left, right;
    for (auto idx : indices)
    {
        str[idx] = '0';
        if (check_element(str))
            left.push_back(idx);
        else
            right.push_back(idx);
        str[idx] = '1';
    }
    int mid = (l + r) / 2;
    query(l, mid, left);
    query(mid, r, right);
}

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