Submission #598496

#	Time	Username	Problem	Language	Result	Execution time	Memory
598496		jophyyjh	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	2 ms	556 KiB

messy

/**
 * 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 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30