Submission #1205178

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

messy

#include "messy.h"

#include <cassert>
#include <iostream>
#include <string>
#include <vector>

void write_specials(int n, int special);
void write_range(int l, int r, int n, int depth);
std::vector<int> find_specials(int n, int special);
void solve_range(int n, int l, int r, int depth, std::vector<int> indexes, std::vector<int> specials, std::vector<int>& ans);

std::vector<int> restore_permutation(int n, int w, int r) {
    int logn = 0;
    while (1 << logn < n) ++logn;
    int special = logn - 1;  // These are calculated explicitly

    write_specials(n, special);
    write_range(special, n - 1, n, 0);
    compile_set();
    std::vector<int> specials = find_specials(n, special);
    std::vector<int> ans(n, -1);
    for (int i = 0; i < special; ++i) ans[specials[i]] = i;
    std::vector<int> nonspecial;
    for (int i = 0; i < n; ++i) {
        if (ans[i] == -1) nonspecial.push_back(i);
    }
    solve_range(n, special, n - 1, 0, nonspecial, specials, ans);

    return ans;
}

void write_specials(int n, int special) {
    for (int i = 0; i < special; ++i) {
        std::string writebuf(n, '1');
        writebuf[i] = '0';
        add_element(writebuf);
    }

    std::string writebuf(n, '0');
    for (int i = 0; i < special; ++i) {
        writebuf[i] = '1';
        add_element(writebuf);
    }
}

void write_range(int l, int r, int n, int depth) {
    // std::cout << "writing range from " << l << " to " << r << " with depth " << depth << '\n';
    if (l > r) return;
    if (l == r) return;
    int m = (l + r - 1) / 2;
    std::string setspecials(n, '0');

    // set first `depth` special bits
    for (int i = 0; i < depth; ++i) {
        setspecials[i] = '1';
    }

    for (int i = l; i <= m; ++i) {
        std::string writebuf = setspecials;
        writebuf[i] = '1';
        add_element(writebuf);
    }

    write_range(l, m, n, depth + 1);
    write_range(m + 1, r, n, depth + 1);
}

std::vector<int> find_specials(int n, int special) {
    std::vector<int> unordered;
    for (int i = 0; i < n; ++i) {
        std::string readbuf(n, '1');
        readbuf[i] = '0';
        if (check_element(readbuf)) {
            unordered.push_back(i);
        }
    }

    std::vector<int> seen(special);
    std::vector<int> ordered;
    for (int i = 0; i < special; ++i) {
        for (int j = 0; j < special; ++j) {
            std::string readbuf = std::string(n, '0');
            for (int k : ordered) {
                readbuf[k] = '1';
            }
            if (seen[j]) continue;
            readbuf[unordered[j]] = '1';
            if (check_element(readbuf)) {
                seen[j] = true;
                ordered.push_back(unordered[j]);
                break;
            }
        }
    }
    return ordered;
}

void solve_range(int n, int l, int r, int depth, std::vector<int> indexes, std::vector<int> specials, std::vector<int>& ans) {
    assert(indexes.size() == r - l + 1);
    if (l > r) return;
    if (l == r) {
        ans[indexes[0]] = l;
        return;
    }

    int m = (l + r - 1) / 2;
    int lcount = m - l + 1;
    std::vector<int> left, right;
    std::string setspecials(n, '0');
    for (int i = 0; i < depth; ++i) setspecials[specials[i]] = '1';
    for (int index : indexes) {
        if (index == indexes.back()) {
            if (left.size() < lcount) {
                left.push_back(index);
            } else {
                right.push_back(index);
            }
            break;
        }
        std::string readbuf = setspecials;
        readbuf[index] = '1';
        if (check_element(readbuf)) {
            left.push_back(index);
        } else {
            right.push_back(index);
        }
    }

    solve_range(n, l, m, depth + 1, left, specials, ans);
    solve_range(n, m + 1, r, depth + 1, right, specials, 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