fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6.  
  7. const int N = 1e5;
  8. const long long M = 1e18, S = (1LL << 59) - 1;
  9.  
  10. mt19937_64 rnd(349237901836100);
  11. long long get_rand(long long l, long long r) {
  12.     assert(l <= r);
  13.     return l + rnd() % (r - l + 1);
  14. }
  15. vector<long long> random(vector<long long> p) {
  16.     shuffle(p.begin(), p.end(), rnd);
  17.     return p;
  18. }
  19. // Returns the immediate next number with same count of one bits, -1 on failure
  20. long long next_one(long long n){
  21.     if (n == 0) return -1;
  22.     long long x = (n & -n);
  23.     long long left = (x + n);
  24.     long long right = ((n ^ left) / x) >> 2;
  25.     long long res = (left | right);
  26.     return res;
  27. }
  28. vector<long long> big(int n) {
  29.     set<long long> se;
  30.     se.insert(0);
  31.     vector<long long> p(n);
  32.     for (int i = 0; i < n; i++) {
  33.         long long z;
  34.         do {
  35.             z = get_rand(1, M);
  36.         } while(se.find(z) != se.end());
  37.         se.insert(z);
  38.         p[i] = z;
  39.     }
  40.     return p;
  41. }
  42. vector<long long> potential_yes1() {
  43.     int n;
  44.     if (rnd() % 2) n = get_rand(50, 59);
  45.     else n = get_rand(20, 49);
  46.     vector<long long> p(n);
  47.     vector<int> perm(59, 0);
  48.     iota(perm.begin(), perm.end(), 0);
  49.     shuffle(perm.begin(), perm.end(), rnd);
  50.     for (int i = 0; i < n; i++) {
  51.         p[i] = 1LL << perm[i];
  52.         for (int k = n; k < 59; k++) {
  53.              p[i] |= 1LL << (perm[k]);
  54.         }
  55.     }
  56.     if (rnd() % 4 == 0) p.push_back(S);
  57.     return random(p);
  58. }
  59. vector<long long> potential_yes2() {
  60.     int n;
  61.     if (rnd() % 2) n = get_rand(50, 59);
  62.     else n = get_rand(20, 49);
  63.     vector<long long> p(n);
  64.     vector<int> perm(59, 0);
  65.     iota(perm.begin(), perm.end(), 0);
  66.     shuffle(perm.begin(), perm.end(), rnd);
  67.     for (int i = 0; i < n; i++) {
  68.         p[i] = 1LL << perm[i];
  69.         for (int k = n; k < 59; k++) {
  70.              if (rnd() % 2) p[i] |= 1LL << (perm[k]);
  71.         }
  72.     }
  73.     if (rnd() % 4 == 0) p.push_back(S);
  74.     return random(p);
  75. }
  76. vector<long long> prefix_defense() {
  77.     int n;
  78.     if (rnd() % 2) n = get_rand(50, 59);
  79.     else n = get_rand(20, 49);
  80.     vector<long long> p(n);
  81.     vector<int> perm(59, 0);
  82.     iota(perm.begin(), perm.end(), 0);
  83.     shuffle(perm.begin(), perm.end(), rnd);
  84.     for (int i = 0; i < n; i++) {
  85.         p[i] = 1LL << perm[i];
  86.         for (int k = n; k < 59; k++) {
  87.              if (rnd() % 2) p[i] |= 1LL << (perm[k]);
  88.         }
  89.         for (int j = 0; j < i; j++) {
  90.             if (rnd() % 4 == 0) p[i] |= 1LL << perm[j];
  91.         }
  92.     }
  93.     if (rnd() % 3 == 0) reverse(p.begin(), p.end());
  94.     return random(p);
  95. }
  96. int32_t main() {
  97.     for (int t = 0; t < 2; t++) {
  98.         auto ttt = clock();
  99.         string zz = t < 10 ? "00" : "0";
  100.         string in = "input" + zz + to_string(t) + ".txt";
  101.         freopen(in.c_str(), "wb", stdout);
  102.         vector<vector<long long>> v;
  103.         if (t == 0) {
  104.             v.push_back({0});
  105.             v.push_back({1});
  106.             v.push_back({M});
  107.             v.push_back({S});
  108.             v.push_back({0, 1});
  109.             v.push_back({0, M});
  110.             v.push_back({0, S});
  111.             v.push_back({S, M});
  112.             v.push_back({1, M});
  113.             v.push_back({1, S});
  114.             v.push_back({1, 2, 7});
  115.             vector<long long> p;
  116.             for (int i = 0; i < 60; i++) p.push_back({1LL << i});
  117.             v.push_back(p);
  118.             v.push_back(random(p));
  119.             p.insert(p.begin() + 30, 0);
  120.             v.push_back(p);
  121.             v.push_back(random(p));
  122.             p.clear();
  123.             for (int i = 1; i < 60; i++) {
  124.                 p.push_back({(1LL << i) - 1});
  125.             }
  126.             v.push_back(p);
  127.             v.push_back(random(p));
  128.             for (int i = 0; i < 250; i++) {
  129.                 v.push_back(potential_yes1());
  130.             }
  131.             p.clear();
  132.             for (int i = 1; i <= N; i++) p.push_back(1LL * i * i * i * 1000);
  133.             v.push_back(random(p));
  134.             v.push_back(big(N));
  135.             int sum = 0;
  136.             for (auto x: v) sum += x.size();
  137.             p.clear();
  138.             long long nw = (1LL << 30) - 1;
  139.             while (sum < 300000) {
  140.                 sum++;
  141.                 p.push_back(nw);
  142.                 nw = next_one(nw);
  143.             }
  144.             for (auto x: p) assert(__builtin_popcountll(x) == __builtin_popcountll(p[0]));
  145.             v.push_back(random(p));
  146.         }
  147.         else {
  148.             for (int i = 0; i < 300; i++) {
  149.                 if (i < 200) v.push_back(potential_yes2());
  150.                 else if (i < 297) v.push_back(prefix_defense());
  151.                 else {
  152.                     int sum = 0;
  153.                     for (auto x: v) sum += x.size();
  154.                     if (sum < 300000) v.push_back(big(min(100000, 300000 - sum)));
  155.                 }
  156.             }
  157.         }
  158.         // assert constraints
  159.         assert(1 <= v.size() && v.size() <= 300);
  160.         cout << v.size() << '\n';
  161.         int sum = 0;
  162.         for (auto x: v) {
  163.             assert(1 <= x.size() && x.size() <= 100000);
  164.             sum += x.size();
  165.             cout << x.size() << '\n';
  166.             for (int i = 0; i < x.size(); i++) {
  167.                 long long y = x[i];
  168.                 assert(0 <= y && y <= M);
  169.                 if (i) cout << ' ';
  170.                 cout << y;
  171.             }
  172.             cout << '\n';
  173.         }
  174.         assert(1 <= sum && sum <= 300000);
  175.         cerr << "Test Case #" << t << " : " << fixed << setprecision(6) << 1.0 * (clock() - ttt) / CLOCKS_PER_SEC << "s\n";
  176.     }
  177.     return 0;
  178. }
Success #stdin #stdout #stderr 0.23s 10544KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Test Case #0 : 0.079254s
Test Case #1 : 0.152015s
https://ideone.com/FyXVT6
language:
C++14 (gcc 8.3)
created:
4 years 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!