fork download 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <cstdint>
  5. #include <sstream>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. const double MAXX = 1e308;
  11. const double MINN = 1e-308;
  12. const int BATCH_SIZE = 8;
  13. const int IDX_BITS = 11;
  14. const int FULL_MASK = (1 << IDX_BITS) - 1;
  15.  
  16. int permute_pow2(int x, int key1, int key2) {
  17.     x &= FULL_MASK;
  18.     x = (x + key1) & FULL_MASK;
  19.     x ^= (x << 5) & FULL_MASK;
  20.     x ^= (x >> 7);
  21.     x = (x + key2) & FULL_MASK;
  22.     x ^= (x << 3) & FULL_MASK;
  23.     x ^= (x >> 2);
  24.     x = (x + (key1 ^ key2)) & FULL_MASK;
  25.     return x & FULL_MASK;
  26. }
  27.  
  28. int permute_restricted(int n, int seed, int idx) {
  29.     int key1 = (seed * 73 + n * 19 + 7) & FULL_MASK;
  30.     int key2 = (seed * 199 + n * 11 + 13) & FULL_MASK;
  31.     int x = idx & FULL_MASK;
  32.  
  33.     for (int i = 0; i < (1 << 12); ++i) {
  34.         x = permute_pow2(x, key1, key2);
  35.         if (x < n) {
  36.             return x;
  37.         }
  38.     }
  39.     return idx % n;
  40. }
  41.  
  42. int encode_state(int seed, int batch) {
  43.     return ((seed & 0xFF) << 8) | (batch & 0xFF);
  44. }
  45.  
  46. pair<int, int> decode_state(int state) {
  47.     int seed = (state >> 8) & 0xFF;
  48.     int batch = state & 0xFF;
  49.     return {seed, batch};
  50. }
  51.  
  52. string handle_init(int n, int &seed_counter) {
  53.     (void)n;
  54.     int seed = seed_counter;
  55.     seed_counter = (seed_counter + 1) & 0xFF;
  56.     if (seed_counter == 0) {
  57.         seed_counter = 1;
  58.     }
  59.     int state = encode_state(seed, 0);
  60.  
  61.     ostringstream out;
  62.     out << "{\"state\":" << state << "}";
  63.     return out.str();
  64. }
  65.  
  66. string handle_next(int n, int state) {
  67.     auto [seed, batch] = decode_state(state);
  68.     int start_idx = batch * BATCH_SIZE;
  69.  
  70.     if (start_idx >= n) {
  71.         ostringstream out;
  72.         out << "{\"state\":" << state << ",\"indices\":[]}";
  73.         return out.str();
  74.     }
  75.  
  76.     int take = min(BATCH_SIZE, n - start_idx);
  77.     vector<int> indices;
  78.     indices.reserve(take);
  79.  
  80.     for (int i = start_idx; i < start_idx + take; ++i) {
  81.         indices.push_back(permute_restricted(n, seed, i));
  82.     }
  83.  
  84.     int new_state = encode_state(seed, batch + 1);
  85.  
  86.     ostringstream out;
  87.     out << "{\"state\":" << new_state << ",\"indices\":[";
  88.     for (int i = 0; i < (int)indices.size(); ++i) {
  89.         if (i > 0) out << ",";
  90.         out << indices[i];
  91.     }
  92.     out << "]}";
  93.     return out.str();
  94. }
  95.  
  96. string trim(const string &s) {
  97.     size_t l = 0;
  98.     while (l < s.size() && isspace((unsigned char)s[l])) ++l;
  99.     size_t r = s.size();
  100.     while (r > l && isspace((unsigned char)s[r - 1])) --r;
  101.     return s.substr(l, r - l);
  102. }
  103.  
  104. string get_json_string_field(const string &line, const string &key) {
  105.     string pattern = "\"" + key + "\"";
  106.     size_t pos = line.find(pattern);
  107.     if (pos == string::npos) return "";
  108.     pos = line.find(':', pos);
  109.     if (pos == string::npos) return "";
  110.     pos = line.find('"', pos);
  111.     if (pos == string::npos) return "";
  112.     size_t end = line.find('"', pos + 1);
  113.     if (end == string::npos) return "";
  114.     return line.substr(pos + 1, end - pos - 1);
  115. }
  116.  
  117. bool get_json_int_field(const string &line, const string &key, long long &value) {
  118.     string pattern = "\"" + key + "\"";
  119.     size_t pos = line.find(pattern);
  120.     if (pos == string::npos) return false;
  121.     pos = line.find(':', pos);
  122.     if (pos == string::npos) return false;
  123.     ++pos;
  124.     while (pos < line.size() && isspace((unsigned char)line[pos])) ++pos;
  125.     if (pos >= line.size()) return false;
  126.     size_t end = pos;
  127.     while (end < line.size() && (isdigit((unsigned char)line[end]) || line[end] == '-' || line[end] == '+')) {
  128.         ++end;
  129.     }
  130.     if (end == pos) return false;
  131.     try {
  132.         value = stoll(line.substr(pos, end - pos));
  133.     } catch (...) {
  134.         return false;
  135.     }
  136.     return true;
  137. }
  138.  
  139. int main() {
  140.     ios::sync_with_stdio(false);
  141.     cin.tie(nullptr);
  142.  
  143.     int seed_counter = 1;
  144.     string line;
  145.  
  146.     while (getline(cin, line)) {
  147.         line = trim(line);
  148.         if (line.empty()) continue;
  149.  
  150.         string rtype = get_json_string_field(line, "type");
  151.         if (rtype.empty()) continue;
  152.  
  153.         string resp;
  154.  
  155.         if (rtype == "ping") {
  156.             resp = "{}";
  157.         } else if (rtype == "init") {
  158.             long long n_ll = 0;
  159.             if (!get_json_int_field(line, "n", n_ll)) {
  160.                 resp = "{}";
  161.             } else {
  162.                 int n = static_cast<int>(n_ll);
  163.                 resp = handle_init(n, seed_counter);
  164.             }
  165.         } else if (rtype == "next") {
  166.             long long n_ll = 0;
  167.             long long state_ll = 0;
  168.             bool ok_n = get_json_int_field(line, "n", n_ll);
  169.             bool ok_state = get_json_int_field(line, "state", state_ll);
  170.             if (!ok_n || !ok_state) {
  171.                 resp = "{}";
  172.             } else {
  173.                 int n = static_cast<int>(n_ll);
  174.                 int state = static_cast<int>(state_ll);
  175.                 resp = handle_next(n, state);
  176.             }
  177.         } else {
  178.             resp = "{}";
  179.         }
  180.  
  181.         cout << resp << "\n";
  182.         cout.flush();
  183.     }
  184.  
  185.     return 0;
  186. }
  187.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/hfT5jm
language:
C++ (gcc 8.3)
created:
1 day 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!