Submission #524257

#TimeUsernameProblemLanguageResultExecution timeMemory
524257tabrUnscrambling a Messy Bug (IOI16_messy)C++17
20 / 100
2 ms460 KiB
#include <bits/stdc++.h> using namespace std; #ifdef tabr #include "library/debug.cpp" #else #define debug(...) #endif #ifdef tabr function<void(string)> add_element; function<void()> compile_set; function<bool(string)> check_element; #else #include "messy.h" #endif vector<int> restore_permutation(int n, int, int) { int k = __builtin_ctz(n); for (int i = 0; i < k; i++) { string s(n, '0'); s[i] = '1'; add_element(s); } for (int i = 0; i < k - 1; i++) { string s(n, '0'); s[i] = s[i + 1] = '1'; add_element(s); } for (int i = k; i < n; i++) { for (int j = 0; j < k; j++) { if (i & (1 << j)) { string s(n, '0'); s[i] = s[j] = '1'; add_element(s); } } } { string s(n, '1'); s[0] = '0'; add_element(s); } compile_set(); vector<int> p(n, -1); set<int> st; for (int i = 0; i < n; i++) { string s(n, '0'); s[i] = '1'; if (check_element(s)) { st.emplace(i); } } debug(st); vector<int> q(k); for (int i : st) { string s(n, '1'); s[i] = '0'; if (check_element(s)) { q[0] = i; st.erase(i); break; } } for (int i = 1; i < k - 1; i++) { for (int j : st) { string s(n, '0'); s[q[i - 1]] = s[j] = '1'; if (check_element(s)) { q[i] = j; st.erase(j); break; } } } q[k - 1] = *st.begin(); for (int i = 0; i < k; i++) { p[q[i]] = i; } for (int i = 0; i < n; i++) { if (p[i] != -1) { continue; } p[i] = 0; for (int j = 0; j < k; j++) { string s(n, '0'); s[i] = s[q[j]] = '1'; if (check_element(s)) { p[i] |= 1 << j; } } } vector<int> res(n); for (int i = 0; i < n; i++) { res[p[i]] = i; } return res; } #ifdef tabr int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count()); vector<int> p(n); iota(p.begin(), p.end(), 0); shuffle(p.begin(), p.end(), rng); vector<string> t; add_element = [&](string x) { debug(x); t.emplace_back(x); }; compile_set = [&]() { for (string& x : t) { string y = x; for (int i = 0; i < n; i++) { x[p[i]] = y[i]; } } sort(t.begin(), t.end()); }; check_element = [&](string x) { return binary_search(t.begin(), t.end(), x); }; debug(p); debug(restore_permutation(n, 0, 0)); return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...