fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // --------- 64-bit deterministic hash (splitmix64) ----------
  5. static inline uint64_t splitmix64(uint64_t x){
  6.     x += 0x9e3779b97f4a7c15ULL;
  7.     x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
  8.     x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
  9.     x ^= (x >> 31);
  10.     return x;
  11. }
  12. // Public hash for number j with small seed s (0..15)
  13. static inline uint64_t H(int j, int s){
  14.     // deterministic, no RNG
  15.     uint64_t x = (uint64_t)j * 0x9e3779b97f4a7c15ULL
  16.                ^ (uint64_t)(s + 0x9e3779b9) * 0xbf58476d1ce4e5b9ULL
  17.                ^ 0x94d049bb133111ebULL;
  18.     return splitmix64(x);
  19. }
  20.  
  21. // --------- XOR linear basis over GF(2) with reconstruction ----------
  22. struct XorBasis {
  23.     // basis[b] has pivot at bit b (0..63)
  24.     uint64_t basis[64]{};
  25.     // comb[b] tells which columns (as bitset) compose basis[b]
  26.     array< bitset<128>, 64 > comb;
  27.  
  28.     void clear(){
  29.         memset(basis, 0, sizeof(basis));
  30.         for(auto &c: comb) c.reset();
  31.     }
  32.  
  33.     // insert vector v with column mask m; returns true if inserted (independent)
  34.     bool insert(uint64_t v, const bitset<128>& m){
  35.         uint64_t x = v;
  36.         bitset<128> mask = m;
  37.         for(int b=63; b>=0; --b){
  38.             if(((x>>b)&1ULL)==0) continue;
  39.             if(!basis[b]){
  40.                 basis[b]=x; comb[b]=mask;
  41.                 return true;
  42.             }
  43.             x ^= basis[b];
  44.             mask ^= comb[b];
  45.         }
  46.         return false; // dependent
  47.     }
  48.  
  49.     // try represent target; if possible, fills mask (which columns XOR to target)
  50.     bool represent(uint64_t target, bitset<128>& mask) const {
  51.         mask.reset();
  52.         uint64_t t = target;
  53.         for(int b=63; b>=0; --b){
  54.             if(((t>>b)&1ULL)==0) continue;
  55.             if(!basis[b]) return false; // cannot reduce this bit
  56.             t ^= basis[b];
  57.             mask ^= comb[b];
  58.         }
  59.         return (t==0);
  60.     }
  61. };
  62.  
  63. int main(){
  64.     ios::sync_with_stdio(false);
  65.     cin.tie(nullptr);
  66.  
  67.     int T; 
  68.     if(!(cin >> T)) return 0;
  69.  
  70.     if(T==1){
  71.         int N; unsigned long long X;
  72.         cin >> N >> X; // N=100, X <= 1e18 < 2^60
  73.         vector<pair<int,int>> card(N);
  74.         for(int i=0;i<N;i++){
  75.             int a,b; cin>>a>>b;
  76.             card[i]={a,b};
  77.         }
  78.  
  79.         // Try seeds s = 0..15. Target encodes [ top4=s | low60=X ].
  80.         const int SEED_BITS = 4;
  81.         const int MAX_SEED = (1<<SEED_BITS);
  82.         uint64_t answer_seed = ULLONG_MAX;
  83.         bitset<128> pickMask; // which columns choose b_i (y_i=1)
  84.         vector<uint64_t> d(N);
  85.         vector<uint64_t> baseHash(N);
  86.  
  87.         // To avoid recomputing too much, we'll loop seeds and solve basis each time.
  88.         for(int s=0; s<MAX_SEED; ++s){
  89.             XorBasis xb; xb.clear();
  90.             uint64_t base = 0;
  91.             for(int i=0;i<N;i++){
  92.                 uint64_t ha = H(card[i].first, s);
  93.                 uint64_t hb = H(card[i].second, s);
  94.                 baseHash[i] = ha;          // assume pick a_i by default
  95.                 d[i] = ha ^ hb;            // column vector for variable y_i
  96.                 base ^= ha;
  97.             }
  98.             uint64_t target = ((uint64_t)s << 60) ^ (uint64_t)X ^ base;
  99.  
  100.             // build basis
  101.             for(int i=0;i<N;i++){
  102.                 bitset<128> col; col.reset(); col.set(i);
  103.                 xb.insert(d[i], col);
  104.             }
  105.             bitset<128> m;
  106.             if(xb.represent(target, m)){
  107.                 answer_seed = (uint64_t)s;
  108.                 pickMask = m;
  109.                 break;
  110.             }
  111.         }
  112.  
  113.         // Extremely unlikely, but as a safety net, if none worked, fall back s=0 and try greedy:
  114.         if(answer_seed == ULLONG_MAX){
  115.             // deterministic fallback: s=0 with basis solve again (should almost never fail)
  116.             int s = 0;
  117.             XorBasis xb; xb.clear();
  118.             uint64_t base=0;
  119.             for(int i=0;i<N;i++){
  120.                 uint64_t ha = H(card[i].first, s);
  121.                 uint64_t hb = H(card[i].second, s);
  122.                 baseHash[i] = ha;
  123.                 d[i] = ha ^ hb;
  124.                 base ^= ha;
  125.             }
  126.             uint64_t target = ((uint64_t)s << 60) ^ (uint64_t)X ^ base;
  127.             for(int i=0;i<N;i++){
  128.                 bitset<128> col; col.reset(); col.set(i);
  129.                 xb.insert(d[i], col);
  130.             }
  131.             bitset<128> m;
  132.             bool ok = xb.represent(target, m);
  133.             // If still not ok, the instance is astronomically unlucky; but we proceed with m as zero.
  134.             if(ok) pickMask = m;
  135.             answer_seed = 0;
  136.         }
  137.  
  138.         // Output selection according to pickMask: 0 -> pick a_i, 1 -> pick b_i
  139.         int s = (int)answer_seed;
  140.         vector<int> out(N);
  141.         for(int i=0;i<N;i++){
  142.             if(pickMask.test(i)) out[i] = card[i].second;
  143.             else                 out[i] = card[i].first;
  144.         }
  145.         for(int i=0;i<N;i++){
  146.             if(i) cout << ' ';
  147.             cout << out[i];
  148.         }
  149.         cout << '\n';
  150.     }
  151.     else if(T==2){
  152.         int N; cin >> N;
  153.         vector<int> xs(N);
  154.         for(int i=0;i<N;i++) cin >> xs[i]; // sorted ascending
  155.  
  156.         const int SEED_BITS = 4;
  157.         const int MAX_SEED = (1<<SEED_BITS);
  158.  
  159.         // Try all seeds; the correct one s will satisfy: (XOR H_s(x_i)) >> 60 == s
  160.         for(int s=0; s<MAX_SEED; ++s){
  161.             uint64_t acc = 0;
  162.             for(int v: xs) acc ^= H(v, s);
  163.             uint64_t seed_top = acc >> 60;
  164.             if((int)seed_top == s){
  165.                 uint64_t X = acc & ((1ULL<<60) - 1ULL);
  166.                 cout << X << '\n';
  167.                 return 0;
  168.             }
  169.         }
  170.         // Practically unreachable; if happens, default to s=0.
  171.         {
  172.             int s = 0;
  173.             uint64_t acc = 0;
  174.             for(int v: xs) acc ^= H(v, s);
  175.             uint64_t X = acc & ((1ULL<<60) - 1ULL);
  176.             cout << X << '\n';
  177.         }
  178.     }
  179.     return 0;
  180. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
2
4
2 3 5 7
stdout
copy 
762047303910507795
https://ideone.com/B3NMYR
language:
C++ (gcc 8.3)
created:
21 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!