Submission #528969

#TimeUsernameProblemLanguageResultExecution timeMemory
528969tabrData Transfer (IOI19_transfer)C++17
0 / 100
10 ms4444 KiB
#include <bits/stdc++.h> using namespace std; #ifdef tabr #include "library/debug.cpp" #else #define debug(...) #endif #ifndef tabr #include "transfer.h" #endif vector<int> get_attachment(vector<int> a) { int n = (int) a.size(); int q = __builtin_popcount(n); int c = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < q; j++) { if ((i + 1) & (1 << j)) { c ^= a[i] << j; } } } for (int i = 0; i < (1 << (q + 1)); i++) { if (__builtin_parity(i) == 0) { if (c == 0) { for (int j = 0; j < q + 1; j++) { if (i & (1 << j)) { a.emplace_back(1); } else { a.emplace_back(0); } } return a; } c--; } } assert(false); return vector<int>(); } vector<int> retrieve(vector<int> a) { int n = 1; int q = 2; while (n + q != (int) a.size()) { n *= 2; n++; q++; } int c = 0; for (int i = n; i < n + q; i++) { c ^= a[i] << (i - n); } return a; if (__builtin_parity(c) == 1) { a.resize(n); return a; } int b = 0; for (int i = 0; i < c; i++) { if (__builtin_parity(i) == 0) { b++; } } for (int i = 0; i < n; i++) { for (int j = 0; j < q; j++) { if ((i + 1) & (1 << j)) { b ^= a[i] << j; } } } if (b > 0) { a[b - 1] ^= 1; } a.resize(n); return a; } mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count()); int rand_int(int a, int b) { // [a, b] return uniform_int_distribution<int>(a, b)(rng); } #ifdef tabr int main() { ios::sync_with_stdio(false); cin.tie(0); int n = 7; int tt = 100000; while (tt--) { vector<int> a(n); for (int i = 0; i < n; i++) { a[i] = rand_int(0, 1); } auto b = get_attachment(a); int pos = rand_int(-1, (int) b.size() - 1); if (pos >= 0) { b[pos] ^= 1; } auto c = retrieve(b); if (a == c) { // cerr << "OK" << endl; } else { cerr << "NG" << endl; debug(pos); debug(a); debug(b); debug(c); } } return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...