oj.uz

Submission #598496

# Submission time Handle Problem Language Result Execution time Memory
598496 2022-07-18T12:12:15 Z jophyyjh Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 2 ms 556 KB 
/**
 * Let's see how we can do this interactive problem (looks like to be the only
 * interactive task in IOI 2016). The grader is non-adaptive, so it's possible to
 * develop randomized solutions. OK, let's see.
 * 
 * Give 10...0, 110...0, 1110...0, ..., 111.10. Can we test one single bit per read
 * operation? Hmmm. To find a random bit in n locations, the expected num is
 * (1+2+3+...+(n-1)+(n-1))/n = ((n+1) * n / 2 - 1) / n = (n+1)/2 - 1/n. To locate
 * all bits, we need (n+1)/2 + n/2 + ... + 2/2 - (sth) ~ (n+3)*n/4-n*log(n) = O(n^2).
 * Too much, of course.
 * 
 * Well, i guess it may be a divide & conquer problem (due to n=2^b,
 * 896 = 128 * log_2(128)). Can i first put in 1111..10000..0 and determine where do
 * the first n/2 1s go? Ah, what about also putting 0111..11000..0? In that way, the
 * difference between the images (of these two strs) would be the position the 1st
 * and (n+1)-th bit end up. Good.
 * 
 * I will now wrap up my solution. Suppose that n=4. We first ask 1000, 0100 and
 * we'll know where the first 2 bits are sent to. (well, we also know about the
 * last 2 bits too.) Then, we ask 1011 and 1110 to know where the 1st and 3rd bits
 * are sent to. Done.
 * 
 * Write op needed: n * log_2(n) / 2    (not tight)
 * Read op needed:  n * log_2(n)        (tight)
 * Implementation 1
*/

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


int n;

void add(int a, int b) {    // [a, b)
    int mid = (a + b) / 2;
    std::string s(n, '1');
    for (int i = a; i < mid; i++) {
        for (int j = a; j < b; j++)
            s[j] = (i == j ? '1' : '0');
        add_element(s);
    }
    if (b - a > 2) {
        add(a, mid);
        add(mid, b);
    }
}

std::vector<int> perm;  // perm[i] = where i is sent to (different from the output)

void solve(int a, int b) {  // [a, b)
    int k = b - a, mid = (a + b) / 2;
    std::string s(n, '1');
    std::set<int> A, B;
    for (int i = a; i < b; i++) {
        for (int j = a; j < b; j++)
            s[perm[j]] = (i == j ? '1' : '0');
        if (check_element(s))
            A.emplace(perm[i]);
    }
    for (int i = a; i < b; i++) {
        if (A.find(perm[i]) == A.end())
            B.emplace(perm[i]);
    }
    assert(int(A.size()) == k / 2 && int(B.size()) == k / 2);
    int i = a;
    for (int v : A)
        perm[i++] = v;
    for (int v : B)
        perm[i++] = v;
    if (b - a > 2) {
        solve(a, mid);
        solve(mid, b);
    }
}

std::vector<int> restore_permutation(int _n, int w, int r) {
    n = _n;
    add(0, n);
    compile_set();
    perm.resize(n);
    for (int i = 0; i < n; i++)
        perm[i] = i;
    solve(0, n);
    std::vector<int> ans(n);
    for (int i = 0; i < n; i++)
        ans[perm[i]] = i;
    return ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 32
2 Correct 1 ms 300 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 296 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 1 ms 300 KB n = 32
9 Correct 1 ms 340 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 1 ms 304 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 1 ms 212 KB n = 32
14 Correct 1 ms 300 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 212 KB n = 32
2 Correct 1 ms 212 KB n = 32
3 Correct 1 ms 300 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 1 ms 296 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 1 ms 300 KB n = 32
12 Correct 1 ms 296 KB n = 32
13 Correct 1 ms 300 KB n = 32
14 Correct 1 ms 212 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 468 KB n = 128
2 Correct 1 ms 468 KB n = 128
3 Correct 2 ms 468 KB n = 128
4 Correct 1 ms 468 KB n = 128
5 Correct 1 ms 468 KB n = 128
6 Correct 2 ms 468 KB n = 128
7 Correct 2 ms 428 KB n = 128
8 Correct 2 ms 468 KB n = 128
9 Correct 2 ms 424 KB n = 128
10 Correct 2 ms 468 KB n = 128
11 Correct 2 ms 468 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 1 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 468 KB n = 128
3 Correct 2 ms 468 KB n = 128
4 Correct 2 ms 424 KB n = 128
5 Correct 2 ms 556 KB n = 128
6 Correct 2 ms 468 KB n = 128
7 Correct 2 ms 428 KB n = 128
8 Correct 2 ms 468 KB n = 128
9 Correct 2 ms 468 KB n = 128
10 Correct 1 ms 468 KB n = 128
11 Correct 1 ms 468 KB n = 128
12 Correct 2 ms 468 KB n = 128
13 Correct 2 ms 468 KB n = 128
14 Correct 2 ms 428 KB n = 128
15 Correct 1 ms 428 KB n = 128