oj.uz

Submission #756001

# Submission time Handle Problem Language Result Execution time Memory
756001 2023-06-10T19:57:24 Z vjudge1 Password (RMI18_password) C++17
50 / 100
 1024 ms 328 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "C:\GCC\debug.h"
#else
#define debug(...) void(42)
#endif

int cnt = 0;

int query(string s);

string guess(int n, int s) {
  string res = "";

  vector<int> freq(s);
  for (int i = 0; i < s; i++) {
    string x = "";
    for (int it = 0; it < n; it++) {
      x += (i + 'a');
    }
    freq[i] = query(x);
  }

  int ptr = 0;
  while (freq[ptr] == 0) {
    ++ptr;
  }
  for (int i = 0; i < freq[ptr]; i++) {
    res += (ptr + 'a');
  }

  int best = query(res);

  for (int i = ptr + 1; i < s; i++) {
    if (freq[i] == 0) {
      continue;
    }
    int cur = i + 'a';

    auto Build = [&](int pos) {
      int it = 0;
      string tmp = "";
      while (it < pos) {
        tmp += res[it];
        ++it;
      }
      tmp += cur;
      while (it < (int) res.length()) {
        tmp += res[it];
        it++;
      }
      return tmp;
    };

    for (int j = 0; j < (int) res.length(); j++) {
      string tmp = Build(j);

      int cB = query(tmp);
      if (best < cB) {
        best = cB;
        swap(res, tmp);

        if (best == n) {
          return res;
        }
      }
    }
    int rem = n - (int) res.length();

    debug(res);
    string nRes = res;
    nRes.insert((int) nRes.length(), rem, cur);
    best = query(nRes);
    if (best == n) {
      return nRes;
    }
    nRes.resize(best);
    swap(nRes, res);
  }
  return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 145 queries.
2 Correct 3 ms 208 KB Guessed the password with 313 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 49 queries.
2 Correct 2 ms 208 KB Guessed the password with 121 queries.
3 Correct 1 ms 208 KB Guessed the password with 93 queries.
4 Correct 2 ms 208 KB Guessed the password with 218 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 312 KB Guessed the password with 4749 queries.
2 Correct 136 ms 320 KB Guessed the password with 10656 queries.
3 Correct 216 ms 320 KB Guessed the password with 14326 queries.
4 Correct 309 ms 328 KB Guessed the password with 20808 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 145 queries.
2 Correct 3 ms 208 KB Guessed the password with 313 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 2 ms 208 KB Guessed the password with 121 queries.
5 Correct 1 ms 208 KB Guessed the password with 93 queries.
6 Correct 2 ms 208 KB Guessed the password with 218 queries.
7 Correct 55 ms 312 KB Guessed the password with 4749 queries.
8 Correct 136 ms 320 KB Guessed the password with 10656 queries.
9 Correct 216 ms 320 KB Guessed the password with 14326 queries.
10 Correct 309 ms 328 KB Guessed the password with 20808 queries.
11 Incorrect 1024 ms 324 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 145 queries.
2 Correct 3 ms 208 KB Guessed the password with 313 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 2 ms 208 KB Guessed the password with 121 queries.
5 Correct 1 ms 208 KB Guessed the password with 93 queries.
6 Correct 2 ms 208 KB Guessed the password with 218 queries.
7 Correct 55 ms 312 KB Guessed the password with 4749 queries.
8 Correct 136 ms 320 KB Guessed the password with 10656 queries.
9 Correct 216 ms 320 KB Guessed the password with 14326 queries.
10 Correct 309 ms 328 KB Guessed the password with 20808 queries.
11 Incorrect 1024 ms 324 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -