Submission #613828

#	Time	Username	Problem	Language	Result	Execution time	Memory
613828		strange420	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	3 ms	468 KiB

messy

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

int writeData(int start, int end, int n) {
    string element = "";
    int mid = (start + end)/2;
    for (int i=0; i<start; i++) element += '1';
    for (int i=start; i<=end; i++) element += '0';
    for (int i=end+1; i<n; i++) element += '1';

    if (end - start == 1) {
        element[start] = '1';
        add_element(element);
        return 1;
    }

    for (int i=start; i<=mid; i++) {
        element[i] = '1';
        add_element(element);
        element[i] = '0';
    }

    return (mid+1-start) + writeData(start, mid, n) + writeData(mid+1, end, n);
}

vector<int> ans;
int readData(int n, int start, int end, set<int> currentRangeIndex) {
    string element = "";

    if (end - start == 1) {
        for (int i=0; i<n; i++) element += '1';
        element[*currentRangeIndex.begin()] = '0';

        if (check_element(element)) {
            ans[*currentRangeIndex.begin()] = end;
            ans[*next(currentRangeIndex.begin(), 1)] = start;
        } else {
            ans[*currentRangeIndex.begin()] = start;
            ans[*next(currentRangeIndex.begin(), 1)] = end;
        }

        return 1;
    }

    for (int i=0; i<n; i++) element += '0';

    int mid = (start + end)/2;
    for (int i=0; i<n; i++)
        if(currentRangeIndex.find(i) == currentRangeIndex.end())
            element[i] = '1';

    set<int> newCurrentRangeIndex;
    for (int i: currentRangeIndex) {
        element[i] = '1';
        if (check_element(element))
            newCurrentRangeIndex.insert(i);
        element[i] = '0';
    }

    set<int> otherCurrentRangeIndex;
    for (int i: currentRangeIndex)
        if (newCurrentRangeIndex.find(i) == newCurrentRangeIndex.end())
            otherCurrentRangeIndex.insert(i);

    return newCurrentRangeIndex.size() + readData(n, start, mid, newCurrentRangeIndex) + readData(n, mid+1, end, otherCurrentRangeIndex);
}

std::vector<int> restore_permutation(int n, int w, int r) {
    assert(writeData(0, n-1, n) <= w);
    compile_set();

    set<int> temp; ans.resize(n);
    for (int i=0; i<n; i++) temp.insert(i);
    assert(readData(n, 0, n-1, temp) <= r);

    return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30