/**
* 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;
}
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |