oj.uz

Submission #613828

# Submission time Handle Problem Language Result Execution time Memory
613828 2022-07-30T11:43:08 Z strange420 Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 3 ms 468 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 8
2 Correct 0 ms 212 KB n = 8
3 Correct 0 ms 212 KB n = 8
4 Correct 0 ms 212 KB n = 8
5 Correct 0 ms 300 KB n = 8
6 Correct 1 ms 212 KB n = 8
7 Correct 0 ms 212 KB n = 8
8 Correct 0 ms 212 KB n = 8
9 Correct 0 ms 304 KB n = 8
10 Correct 0 ms 212 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 0 ms 212 KB n = 8
13 Correct 0 ms 212 KB n = 8
14 Correct 0 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB n = 32
2 Correct 1 ms 212 KB n = 32
3 Correct 1 ms 212 KB n = 32
4 Correct 1 ms 212 KB n = 32
5 Correct 1 ms 212 KB n = 32
6 Correct 1 ms 304 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 1 ms 212 KB n = 32
9 Correct 1 ms 212 KB n = 32
10 Correct 1 ms 296 KB n = 32
11 Correct 1 ms 212 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 0 ms 212 KB n = 32
14 Correct 0 ms 212 KB n = 32
15 Correct 1 ms 212 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB n = 32
2 Correct 1 ms 308 KB n = 32
3 Correct 1 ms 212 KB n = 32
4 Correct 1 ms 212 KB n = 32
5 Correct 1 ms 212 KB n = 32
6 Correct 1 ms 212 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 1 ms 212 KB n = 32
9 Correct 0 ms 296 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 1 ms 212 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 1 ms 212 KB n = 32
14 Correct 1 ms 296 KB n = 32
15 Correct 1 ms 212 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 428 KB n = 128
2 Correct 2 ms 468 KB n = 128
3 Correct 2 ms 428 KB n = 128
4 Correct 2 ms 428 KB n = 128
5 Correct 2 ms 468 KB n = 128
6 Correct 2 ms 468 KB n = 128
7 Correct 2 ms 468 KB n = 128
8 Correct 2 ms 468 KB n = 128
9 Correct 2 ms 468 KB n = 128
10 Correct 3 ms 468 KB n = 128
11 Correct 2 ms 468 KB n = 128
12 Correct 2 ms 428 KB n = 128
13 Correct 2 ms 468 KB n = 128
14 Correct 2 ms 468 KB n = 128
15 Correct 2 ms 468 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB n = 128
2 Correct 2 ms 428 KB n = 128
3 Correct 2 ms 468 KB n = 128
4 Correct 2 ms 468 KB n = 128
5 Correct 2 ms 468 KB n = 128
6 Correct 2 ms 468 KB n = 128
7 Correct 2 ms 468 KB n = 128
8 Correct 2 ms 468 KB n = 128
9 Correct 2 ms 468 KB n = 128
10 Correct 2 ms 468 KB n = 128
11 Correct 2 ms 428 KB n = 128
12 Correct 2 ms 468 KB n = 128
13 Correct 2 ms 468 KB n = 128
14 Correct 2 ms 468 KB n = 128
15 Correct 2 ms 428 KB n = 128