제출 #704031

#제출 시각아이디문제언어결과실행 시간메모리
704031SamNguyenUnscrambling a Messy Bug (IOI16_messy)C++14
49 / 100
1 ms304 KiB
#include <vector> #include "messy.h" #include <bits/stdc++.h> using namespace std; namespace subtask_1 { const int N = 8, W = 256, R = 256; vector<int> perm; string get_str(int l, int r) { int m = (l + r) >> 1; string str(N, '0'); fill(str.begin() + l, str.begin() + m + 1, '1'); return str; } template <class F> void traverse_tree(F f, int l = 0, int r = N - 1) { if (l == r) return; bool ok = f(l, r); if (not ok) return; int m = (l + r) >> 1; traverse_tree(f, l, m); traverse_tree(f, m + 1, r); } void add_elements() { traverse_tree([&](int l, int r) { add_element(get_str(l, r)); return true; }); } void check_elements() { vector<int> inds; traverse_tree([&](int l, int r) { string str = get_str(l, r); int m = (l + r) >> 1; for (int i = l; i <= m; i++) for (int j = m + 1; j <= r; j++) { swap(str[i], str[j]); if (check_element(str)) { inds = {i, j}; return false; } swap(str[i], str[j]); } return true; }); perm.resize(N); iota(perm.begin(), perm.end(), 0); if (not inds.empty()) swap(perm[inds.front()], perm[inds.back()]); return; } vector<int> restore_permutation() { add_elements(); compile_set(); check_elements(); return perm; } }; namespace subtask_2 { int N, W, R; vector<int> perm, inds; void add_elements() { inds.resize(N); iota(inds.begin(), inds.end(), 0); shuffle(inds.begin(), inds.end(), mt19937(0)); string tmp(N, '0'); for (int i : inds) { tmp[i] = '1'; add_element(tmp); } } void check_elements() { perm.resize(N); string tmp(N, '0'); for (int i : inds) { for (int x : inds) if (tmp[x] == '0') { tmp[x] ^= 1; if (check_element(tmp)) { perm[x] = i; //cout << "perm[" << x << "] = " << i << endl; break; } tmp[x] ^= 1; } } } vector<int> restore_permutation(int n, int w, int r) { N = n, W = w, R = r; add_elements(); compile_set(); check_elements(); return perm; } }; namespace subtask_full { vector<int> perm; void add_elements() { } void check_elements() { } vector<int> restore_permutation(int n, int w, int r) { return perm; } }; vector<int> restore_permutation(int n, int w, int r) { /* if (n == 8 and w == 256 and r == 256) return subtask_1::restore_permutation(); */ //if (n == 32) return subtask_2::restore_permutation(n, w, r); return subtask_full::restore_permutation(n, w, r); }
#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...