#include "message.h" //ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39] //Author: Sazid Hasan #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double dl; typedef vector<int> vi; typedef vector<vector<int>> vii; typedef vector<ll> vl; typedef vector<bool> vb; typedef pair<int,int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second #define all(a) a.begin(),a.end() #define gcd(a,b) __gcd(a,b) #define lcm(a,b) (a*(b/gcd(a,b))) #define spc " " #ifdef ONLINE_JUDGE #define debarr(array) #define deb(x) #define del #else #define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl; #define deb(x) cerr << #x << " = " << x << endl; #define del cerr << '\n'; #endif // const double PI = acos(-1); // const int MOD = 1000000007; // const int inf = (2147483647); const ll C = 1000003; const ll x = 1234567; const ll y = 7654321; const ll z = 42; const ll MOD1 = 1000000007; const ll MOD2 = 1000000009; const ll MOD3 = 998244353; ll binexp_msb(ll base, ll exp, ll mod) { base %= mod; ll res = 1; int highest = 63 - __builtin_clzll(exp); for (int b = highest; b >= 0; --b) { res = (res * res) % mod; if (exp & (1LL << b)) { res = (res * base) % mod; } } return res; } int compute_bit(ll i, ll j) { ll a = binexp_msb(C, 5 * i * j + z, MOD1); ll b = binexp_msb(C, 5 * i * x + z, MOD2); ll c = binexp_msb(C, 5 * j * y + z, MOD3); ll sum = a + b + c + z; return sum & 1; } const int confirmation = 50; void send_message(std::vector<bool> M, std::vector<bool> C) { std::vector<bool> A(31, 0); for(int i = 1; i <= confirmation; i++){ for(int j = 0; j < 31; j++){ A[j] = compute_bit(i, j); } send_packet(A); } A.assign(31, 0); int n = M.size(); for(int i = 30; i >= 0; i--){ if(C[i]==0){ A[i] = n&1; n >>= 1; } if(n==0) break; } send_packet(A); int now = 0, i = 0; int cnt = 0; while(i<M.size()){ if(now!=0 && now%31==0){ send_packet(A); cnt++; } if(C[now%31]==0){ A[now%31] = M[i]; i++; } now++; } send_packet(A); return; } std::vector<bool> receive_message(std::vector<std::vector<bool>> R) { vector<bool> C(31, 1); for(int i = 1; i <= confirmation; i++){ for(int j = 0; j < 31; j++){ C[j] = C[j] & compute_bit(i, j)==R[i-1][j]; } } int n = 0; for(int i = 0; i < 31; i++){ if(C[i]==1){ n <<= 1; n += R[confirmation][i]; } } vb ans(n); int now = 0; for(int i = confirmation+1; i < R.size() && now<n; i++){ for(int j = 0; j < 31 && now<n; j++){ if(C[j]) ans[now] = R[i][j], now++; } } return ans; }