fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. struct custom_hash {
  8.     static uint64_t splitmix64(uint64_t x) {
  9.         x += 0x9e3779b97f4a7c15;
  10.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  11.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  12.         return x ^ (x >> 31);
  13.     }
  14.     size_t operator()(uint64_t x) const {
  15.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  16.         return splitmix64(x + FIXED_RANDOM);
  17.     }
  18. };
  19.  
  20. long long a[45];
  21.  
  22. int main() {
  23.     ios_base::sync_with_stdio(0); 
  24.     cin.tie(0); 
  25.     cout.tie(0);
  26.  
  27.     int n;
  28.     if (!(cin >> n)) return 0;
  29.     for (int i = 0; i < n; i++) cin >> a[i];
  30.  
  31.     gp_hash_table<long long, long long, custom_hash> mp;
  32.     mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  33.  
  34.     while (true) {
  35.         long long mask = rng() & ((1ULL << n) - 1);
  36.         if (mask == 0) continue;
  37.  
  38.         long long sum = 0;
  39.         for (int i = 0; i < n; i++) {
  40.             if ((mask >> i) & 1) sum += a[i];
  41.         }
  42.  
  43.         if (mp.find(sum) != mp.end()) {
  44.             long long m1 = mask;
  45.             long long m2 = mp[sum];
  46.  
  47.             if (m1 != m2) {
  48.                 long long c = m1 & m2;
  49.                 m1 ^= c;
  50.                 m2 ^= c;
  51.  
  52.                 vector<long long> v1, v2;
  53.                 for (int i = 0; i < n; i++) {
  54.                     if ((m1 >> i) & 1) v1.push_back(a[i]);
  55.                     if ((m2 >> i) & 1) v2.push_back(a[i]);
  56.                 }
  57.  
  58.                 cout << v1.size() << "\n";
  59.                 for (int i = 0; i < v1.size(); i++) cout << v1[i] << (i + 1 == v1.size() ? "" : " ");
  60.                 cout << "\n";
  61.  
  62.                 cout << v2.size() << "\n";
  63.                 for (int i = 0; i < v2.size(); i++) cout << v2[i] << (i + 1 == v2.size() ? "" : " ");
  64.                 cout << "\n";
  65.  
  66.                 return 0;
  67.             }
  68.         } else {
  69.             mp[sum] = mask;
  70.         }
  71.     }
  72. }
  73.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AVOJDJ
language:
C++14 (clang 8.0)
created:
7 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!