Submission #1246514

#TimeUsernameProblemLanguageResultExecution timeMemory
1246514flappybirdMessage (IOI24_message)C++20
10 / 100
1705 ms860 KiB
#include "message.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; int B[40][40]; int mxval[5]; int val[5]; int lv[40]; int isval[40]; void init() { int i, j; for (i = 0; i <= 32; i++) { for (j = 0; j <= i; j++) { if (i == j || i == 0 || j == 0) B[i][j] = 1; else B[i][j] = B[i - 1][j] + B[i - 1][j - 1]; } } } void init_A() { int i; init(); memset(mxval, 0, sizeof(mxval)); memset(lv, 0, sizeof(lv)); for (i = 0; i < 4; i++) mxval[i] = B[1 << (4 - i)][1 << (3 - i)]; } void init_B() { int i; init(); memset(lv, 0, sizeof(isval)); } void send_message(std::vector<bool> M, std::vector<bool> C) { init_A(); M.push_back(1); M.resize(1025); int i; int lastbit = 0; for (i = 0; i < 24; i++) if (M[M.size() - 24 + i]) lastbit |= (1 << i); M.resize(M.size() - 24); for (i = 3; i >= 0; i--) { val[i] = lastbit % mxval[i]; lastbit /= mxval[i]; } assert(lastbit == 0); int ptr = 0; auto getnext = [&]() { if (ptr >= M.size()) return false; return (bool)M[ptr++]; }; int d; //for (i = 0; i < 31; i++) if (!C[i]) lv[i] = 0; for (d = 0; d < 4; d++) { vector<bool> v; int N = 1 << (3 - d); //len: 2N, choose N indexes for (i = 0; i < N; i++) v.push_back(0); for (i = 0; i < N; i++) v.push_back(1); for (i = 0; i < val[d]; i++) next_permutation(v.begin(), v.end()); int p = 0; vector<bool> sv(31); for (i = 0; i < 31; i++) if (!C[i]) { if (lv[i] == d) sv[i] = v[p++]; else sv[i] = getnext(); } auto res = send_packet(sv); int cnt[2] = { 0, 0 }; for (i = 0; i < 31; i++) if (lv[i] == d && C[i]) cnt[res[i]]++; int c = 0; if (cnt[0] > cnt[1]) c = 1; for (i = 0; i < 31; i++) if (lv[i] == d && res[i] == c) lv[i]++; } int key = 0; for (i = 0; i < 31; i++) { if (lv[i] == 4) { key = i; break; } } for (d = 0; d < 4; d++) val[d] = 0; for (d = 0; d < 4; d++) { int t, f; t = f = 0; vector<int> v; for (i = 0; i < 31; i++) if (lv[i] == d) { v.push_back(C[i]); if (C[i]) f++; else t++; } mxval[d] = B[t + f][t]; while (prev_permutation(v.begin(), v.end())) val[d]++; } int sum = 0; for (i = 0; i < 4; i++) { sum *= mxval[i]; sum += val[i]; } int rem = 24; while (ptr < M.size()) { vector<bool> sv(31); for (i = 0; i < 31; i++) { if (C[i]) continue; if (i == key && rem) { rem--; sv[i] = sum & 1; sum >>= 1; } else sv[i] = getnext(); } send_packet(sv); } } std::vector<bool> receive_message(std::vector<std::vector<bool>> R) { init_B(); int d, i; for (d = 0; d < 4; d++) { int cnt[2] = { 0, 0 }; for (i = 0; i < 31; i++) if (lv[i] == d) cnt[R[d][i]]++; int c = 0; if (cnt[0] > cnt[1]) c = 1; for (i = 0; i < 31; i++) if (lv[i] == d && R[d][i] == c) lv[i]++; } int key = 0; int lcnt[4] = { 0, 0, 0, 0 }; for (i = 0; i < 31; i++) { if (lv[i] == 4) key = i; else lcnt[lv[i]]++; } for (i = 0; i < 4; i++) mxval[i] = B[lcnt[i]][1 << (3 - i)]; int mul = 0; for (i = 0; i < 24; i++) if (R[i + 4][key]) mul |= (1 << i); for (i = 3; i >= 0; i--) { val[i] = mul % mxval[i]; mul /= mxval[i]; } isval[key] = 1; for (d = 0; d < 4; d++) { vector<int> v(lcnt[d], 1); for (i = 0; i < (1 << 3 - d); i++) v[i] = 0; for (i = 0; i < val[d]; i++) next_permutation(v.begin(), v.end()); int p = 0; for (i = 0; i < 31; i++) if (lv[i] == d) isval[i] = 1 - v[p++]; } vector<bool> ans; for (d = 1; d < 4; d++) { for (i = 0; i < 31; i++) { if (isval[i] && lv[i] < d) { ans.push_back(R[d][i]); } } } for (d = 4; d < R.size(); d++) { for (i = 0; i < 31; i++) if (isval[i]) { if (i == key && d < 28) continue; ans.push_back(R[d][i]); } } assert(ans.size() >= 1002); ans.resize(1002); for (i = 0; i < 4; i++) mxval[i] = B[1 << (4 - i)][1 << (3 - i)]; for (d = 0; d < 4; d++) { vector<int> v; for (i = 0; i < 31; i++) if (isval[i] && lv[i] >= d) v.push_back(R[d][i]); val[d] = 0; while (prev_permutation(v.begin(), v.end())) val[d]++; } int lastbit = 0; for (i = 0; i < 4; i++) { lastbit *= mxval[i]; lastbit += val[i]; } for (i = 0; i < 24; i++) { ans.push_back(lastbit & 1); lastbit >>= 1; } while (!ans.back()) ans.pop_back(); ans.pop_back(); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...