# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
747716 | 2023-05-24T14:40:38 Z | _martynas | Unscrambling a Messy Bug (IOI16_messy) | C++11 | 2 ms | 496 KB |
#include <bits/stdc++.h> #include "messy.h" using namespace std; #define PB push_back using vi = vector<int>; struct Group { vi from, to; }; vi restore_permutation(int n, int w, int r) { /* add_element("0"); compile_set(); check_element("0"); */ int B = __builtin_ctz(n); for(int b = B; b >= 1; b--) { for(int i = 0; i < n; i += 1<<b) { for(int j = i; j < i+(1<<b)/2; j++) { string s(n, '1'); fill(s.begin()+i, s.begin()+i+(1<<b), '0'); s[j] = '1'; add_element(s); } } } compile_set(); vector<Group> G; { Group g; for(int i = 0; i < n; i++) g.from.PB(i), g.to.PB(i); G.PB(g); } for(int b = B; b >= 1; b--) { vector<Group> Gp; for(auto g : G) { // from should be consecutive positions vi set_bits, unset_bits; for(int i : g.to) { string s(n, '1'); for(int j : g.to) s[j] = '0'; s[i] = '1'; bool resp = check_element(s); if(resp) { set_bits.PB(i); } else { unset_bits.PB(i); } } Group gl, gr; for(int i = 0; i < g.from.size(); i++) { if(i < g.from.size()/2) { gl.from.PB(g.from[i]); gl.to.PB(set_bits[i]); } else { gr.from.PB(g.from[i]); gr.to.PB(unset_bits[i - g.from.size()/2]); } } Gp.PB(gl); Gp.PB(gr); } G = Gp; } vi ans(n); for(int i = 0; i < n; i++) { ans[G[i].to[0]] = G[i].from[0]; } return ans; } /* 4 100 100 2 1 3 0 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | n = 8 |
2 | Correct | 1 ms | 212 KB | n = 8 |
3 | Correct | 1 ms | 304 KB | n = 8 |
4 | Correct | 1 ms | 212 KB | n = 8 |
5 | Correct | 1 ms | 300 KB | n = 8 |
6 | Correct | 0 ms | 212 KB | n = 8 |
7 | Correct | 1 ms | 212 KB | n = 8 |
8 | Correct | 1 ms | 212 KB | n = 8 |
9 | Correct | 1 ms | 212 KB | n = 8 |
10 | Correct | 1 ms | 212 KB | n = 8 |
11 | Correct | 1 ms | 212 KB | n = 8 |
12 | Correct | 1 ms | 212 KB | n = 8 |
13 | Correct | 1 ms | 300 KB | n = 8 |
14 | Correct | 1 ms | 212 KB | n = 8 |
15 | Correct | 1 ms | 340 KB | n = 8 |
# | 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 | 212 KB | n = 32 |
4 | Correct | 1 ms | 296 KB | n = 32 |
5 | Correct | 1 ms | 300 KB | n = 32 |
6 | Correct | 1 ms | 212 KB | n = 32 |
7 | Correct | 1 ms | 296 KB | n = 32 |
8 | Correct | 1 ms | 212 KB | n = 32 |
9 | Correct | 1 ms | 212 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 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | n = 32 |
2 | Correct | 1 ms | 284 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 | 212 KB | n = 32 |
9 | Correct | 1 ms | 212 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 | 212 KB | n = 32 |
15 | Correct | 1 ms | 300 KB | n = 32 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 468 KB | n = 128 |
2 | Correct | 2 ms | 468 KB | n = 128 |
3 | Correct | 2 ms | 428 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 | 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 | 2 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 | 428 KB | n = 128 |
5 | Correct | 2 ms | 432 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 | 468 KB | n = 128 |
12 | Correct | 2 ms | 424 KB | n = 128 |
13 | Correct | 2 ms | 496 KB | n = 128 |
14 | Correct | 2 ms | 468 KB | n = 128 |
15 | Correct | 2 ms | 428 KB | n = 128 |