Submission #1164436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164436		nguyentunglam	Password (RMI18_password)	C++17	0 / 100	11 ms	460 KiB

password

#include<bits/stdc++.h>
using namespace std;

mt19937_64 rng(1);

long long random(long long l, long long r) {
    return l + rng() % (r - l + 1);
}

int query(string q);

string guess (int n, int s) {
    string answer;
    vector<int> initCnt(s);
    for (int j = 0; j < s; j++) {
      char c = 'a' + j;
      string ask;
      for (int i = 0; i < n; i++) {
        ask.push_back(c);
      }
      initCnt[j] = query(ask);
    }
    vector<int> missingLeftCnt(s), missingRightCnt(s);
    auto solve = [&] (auto solve, vector<int> cnt) -> void {
      int sum = 0;
      for (int i = 0; i < s; i++) {
        sum += cnt[i];
      }
      if (sum == 0) return;
      int randomValue = random(1, sum);
      vector<int> leftCnt(s), rightCnt(s);
      pair<int, int> pivot;
      for (int i = 0; i < s; i++) {
        if (randomValue <= cnt[i]) {
          pivot = {i, randomValue};
          break;
        }
        randomValue -= cnt[i];
      }
      leftCnt[pivot.first] = pivot.second - 1;
      rightCnt[pivot.first] = cnt[pivot.first] - pivot.second;
      string ask;
      for (int i = 0; i < pivot.second + missingLeftCnt[pivot.first]; i++) {
        ask.push_back('a' + pivot.first);
      }
      for (int i = 0; i < s; i++) if (cnt[i]) {
        if (i == pivot.first) continue;
        string _ask = ask;
        for (int j = 0; j < cnt[i] + missingRightCnt[i]; j++) {
          _ask.push_back('a' + i);
        }
        rightCnt[i] = max(0, query(_ask) - pivot.second - missingLeftCnt[pivot.first] - missingRightCnt[i]);
        leftCnt[i] = cnt[i] - rightCnt[i];
      }
      for (int i = 0; i < s; i++) missingRightCnt[i] += rightCnt[i];
      missingRightCnt[pivot.first]++;
      solve(solve, leftCnt);
      for (int i = 0; i < s; i++) missingRightCnt[i] -= rightCnt[i];
      missingRightCnt[pivot.first]--;
      answer.push_back('a' + pivot.first);
      for (int i = 0; i < s; i++) missingLeftCnt[i] += leftCnt[i];
      missingLeftCnt[pivot.first]++;
      solve(solve, rightCnt);
      for (int i = 0; i < s; i++) missingLeftCnt[i] -= leftCnt[i];
      missingLeftCnt[pivot.first]--;
    };
  
    solve(solve, initCnt);
  
    return answer;
  }
  

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20