Submission #853680

#TimeUsernameProblemLanguageResultExecution timeMemory
853680hngwlogUnscrambling a Messy Bug (IOI16_messy)C++14
100 / 100
2 ms604 KiB
#include <bits/stdc++.h> #include "messy.h" using namespace std; #define fi first #define se second #define _size(x) (int)x.size() #define BIT(i, x) ((x >> i) & 1) #define MASK(n) ((1 << n) - 1) #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++) #define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++) #define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--) #define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i) #define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i) #define FORALL(i, a) for (auto i: a) #define fastio ios_base::sync_with_stdio(0); cin.tie(0); vector<int> ans; void add(int n, vector<int> g) { if (_size(g) == 1) return ; vector<int> used(n); string s = ""; REP(i, n) s += '0'; FORALL(pos, g) s[pos] = '1'; REP(i, _size(g) / 2) { used[g[i]]++; s[g[i]] = '0'; add_element(s); s[g[i]] = '1'; } vector<int> newG; FORALL(pos, g) if (used[pos]) newG.push_back(pos); add(n, newG); newG.clear(); FORALL(pos, g) if (!used[pos]) newG.push_back(pos); add(n, newG); } void solve(int n, vector<int> g, vector<int> _g) { if (_size(g) == 1) { ans[_g.back()] = g.back(); return ; } vector<int> used(n), _used(n); REP(i, _size(g) / 2) used[g[i]]++; string t = ""; REP(i, n) t += '0'; FORALL(pos, _g) t[pos] = '1'; FORALL(pos, _g) { t[pos] = '0'; if (check_element(t)) _used[pos]++; t[pos] = '1'; } vector<int> newG, _newG; FORALL(pos, g) if (used[pos]) newG.push_back(pos); FORALL(pos, _g) if (_used[pos]) _newG.push_back(pos); solve(n, newG, _newG); newG.clear(); _newG.clear(); FORALL(pos, g) if (!used[pos]) newG.push_back(pos); FORALL(pos, _g) if (!_used[pos]) _newG.push_back(pos); solve(n, newG, _newG); } vector<int> restore_permutation(int n, int w, int r) { ans.resize(n); vector<int> g, _g; REP(i, n) g.push_back(i), _g.push_back(i); add(n, g); compile_set(); solve(n, g, _g); return ans; }
#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...