# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
298336 | 2020-09-12T17:40:49 Z | Hideo | Unscrambling a Messy Bug (IOI16_messy) | C++11 | 4 ms | 384 KB |
#include "messy.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; #define ll long long #define mk make_pair #define fr first #define sc second #define pb push_back #define vi vector < int > #define pi pair < int, int > const int N = 256; int x[N], us[N], go[N], rv[N], sz; vi ans; vi restore_permutation(int n, int w, int r){ srand(time(NULL)); if (n == 128) sz = 11; else sz = 4; for (int i = 1; i <= n; i++) x[i] = i; random_shuffle(x + 1, x + n + 1); for (int i = 1; i <= n; i++) rv[x[i]] = i; int cc = 0; for (int i = 1; i <= n; i++){ if (i > (cc + 1) * sz) cc++; string s = ""; for (int j = 1; j <= n; j++){ if (x[j] <= cc * sz || x[j] == i) s += '1'; else s += '0'; } add_element(s); } for (int j = 1; j <= n; j++){ string s = ""; if (j % sz == 1){ for (int i = 1; i <= n; i++){ if (x[i] <= j) s += '0'; else s += '1'; } } else { for (int i = 1; i <= n; i++){ if (x[i] <= j) s += '1'; else s += '0'; } } add_element(s); } compile_set(); set < int > st; for (int i = 1; i <= n; i++) st.insert(i); for (int i = 1; i <= n; i += sz){ int r = min(i + sz - 1, n); set < int > cur; for (int it : st){ if (cur.size() == sz) break; string s = ""; for (int m = 1; m <= n; m++){ if (us[m] || m == it) s += '1'; else s += '0'; } if (check_element(s)) cur.insert(it); } for (int it : cur) st.erase(it); for (int j = i; j < r; j++){ int f = 0; for (int it : cur){ if (it == *cur.rbegin()){ f = it; break; } string s = ""; for (int m = 1; m <= n; m++){ if ((j == i && (us[m] || m == it)) || (j != i && !us[m] && m != it)) s += '0'; else s += '1'; } if (check_element(s)){ f = it; break; } } cur.erase(f); us[f] = rv[j]; } us[*cur.begin()] = rv[r]; cur.erase(*cur.begin()); } for (int i = 1; i <= n; i++) ans.pb(us[i] - 1); return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | n = 8 |
2 | Correct | 0 ms | 256 KB | n = 8 |
3 | Correct | 0 ms | 256 KB | n = 8 |
4 | Correct | 0 ms | 256 KB | n = 8 |
5 | Correct | 0 ms | 256 KB | n = 8 |
6 | Correct | 0 ms | 384 KB | n = 8 |
7 | Correct | 1 ms | 384 KB | n = 8 |
8 | Correct | 0 ms | 256 KB | n = 8 |
9 | Correct | 1 ms | 256 KB | n = 8 |
10 | Correct | 1 ms | 256 KB | n = 8 |
11 | Correct | 1 ms | 256 KB | n = 8 |
12 | Correct | 1 ms | 256 KB | n = 8 |
13 | Correct | 0 ms | 256 KB | n = 8 |
14 | Correct | 0 ms | 384 KB | n = 8 |
15 | Correct | 0 ms | 256 KB | n = 8 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | n = 32 |
2 | Correct | 1 ms | 384 KB | n = 32 |
3 | Correct | 1 ms | 384 KB | n = 32 |
4 | Correct | 1 ms | 384 KB | n = 32 |
5 | Correct | 1 ms | 384 KB | n = 32 |
6 | Correct | 1 ms | 384 KB | n = 32 |
7 | Correct | 1 ms | 384 KB | n = 32 |
8 | Correct | 1 ms | 384 KB | n = 32 |
9 | Correct | 1 ms | 384 KB | n = 32 |
10 | Correct | 1 ms | 384 KB | n = 32 |
11 | Correct | 1 ms | 384 KB | n = 32 |
12 | Correct | 1 ms | 384 KB | n = 32 |
13 | Correct | 1 ms | 384 KB | n = 32 |
14 | Correct | 1 ms | 384 KB | n = 32 |
15 | Correct | 1 ms | 384 KB | n = 32 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | n = 32 |
2 | Correct | 1 ms | 384 KB | n = 32 |
3 | Correct | 1 ms | 384 KB | n = 32 |
4 | Correct | 1 ms | 384 KB | n = 32 |
5 | Correct | 1 ms | 384 KB | n = 32 |
6 | Correct | 1 ms | 384 KB | n = 32 |
7 | Correct | 1 ms | 384 KB | n = 32 |
8 | Correct | 1 ms | 384 KB | n = 32 |
9 | Correct | 1 ms | 384 KB | n = 32 |
10 | Correct | 1 ms | 384 KB | n = 32 |
11 | Correct | 1 ms | 384 KB | n = 32 |
12 | Correct | 1 ms | 384 KB | n = 32 |
13 | Correct | 1 ms | 384 KB | n = 32 |
14 | Correct | 1 ms | 384 KB | n = 32 |
15 | Correct | 1 ms | 384 KB | n = 32 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | n = 128 |
2 | Correct | 3 ms | 384 KB | n = 128 |
3 | Correct | 3 ms | 384 KB | n = 128 |
4 | Correct | 3 ms | 384 KB | n = 128 |
5 | Correct | 3 ms | 384 KB | n = 128 |
6 | Correct | 3 ms | 384 KB | n = 128 |
7 | Correct | 3 ms | 384 KB | n = 128 |
8 | Correct | 4 ms | 384 KB | n = 128 |
9 | Correct | 3 ms | 384 KB | n = 128 |
10 | Correct | 4 ms | 384 KB | n = 128 |
11 | Correct | 3 ms | 384 KB | n = 128 |
12 | Correct | 3 ms | 384 KB | n = 128 |
13 | Correct | 3 ms | 384 KB | n = 128 |
14 | Correct | 3 ms | 384 KB | n = 128 |
15 | Correct | 3 ms | 384 KB | n = 128 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 384 KB | grader returned WA |
2 | Halted | 0 ms | 0 KB | - |