oj.uz

Submission #520400

# Submission time Handle Problem Language Result Execution time Memory
520400 2022-01-29T18:47:01 Z Alex_tz307 Password (RMI18_password) C++17
100 / 100
 263 ms 704 KB 
#include <bits/stdc++.h>

using namespace std;

struct sir {
  string s;

  sir() : s("") {}

  bool operator < (const sir &a) const {
    return s.size() > a.s.size();
  };
};

int query(string);

string guess(int n, int m) {
  priority_queue<sir> pq;
  int sum_freq = 0;
  for (int i = 0; i <= m - 1; ++i) {
    char c = i + 97;
    int freq;
    if (i <= m - 2) {
      string aux = "";
      for (int j = 0; j <= n - 1; ++j) {
        aux += c;
      }
      freq = query(aux);
      sum_freq += freq;
    } else {
      freq = n - sum_freq;
    }
    sir a;
    for (int j = 0; j <= freq - 1; ++j) {
      a.s += c;
    }
    pq.push(a);
  }
  while ((int)pq.size() >= 2) {
    sir a = pq.top();
    pq.pop();
    sir b = pq.top();
    pq.pop();
    sir c;
    while (a.s.empty() == false && b.s.empty() == false) {
      string aux = "";
      aux += c.s;
      aux += a.s[0];
      aux += b.s;
      if (query(aux) == 1 + c.s.size() + b.s.size()) {
        c.s += a.s[0];
        a.s.erase(a.s.begin());
      } else {
        c.s += b.s[0];
        b.s.erase(b.s.begin());
      }
    }
    c.s += a.s;
    c.s += b.s;
    pq.push(c);
  }
  return pq.top().s;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |       if (query(aux) == 1 + c.s.size() + b.s.size()) {
      |           ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 56 queries.
2 Correct 2 ms 200 KB Guessed the password with 104 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 48 queries.
2 Correct 1 ms 200 KB Guessed the password with 89 queries.
3 Correct 1 ms 200 KB Guessed the password with 91 queries.
4 Correct 2 ms 200 KB Guessed the password with 177 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 304 KB Guessed the password with 2749 queries.
2 Correct 37 ms 312 KB Guessed the password with 5070 queries.
3 Correct 42 ms 564 KB Guessed the password with 4586 queries.
4 Correct 78 ms 348 KB Guessed the password with 8083 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 56 queries.
2 Correct 2 ms 200 KB Guessed the password with 104 queries.
3 Correct 1 ms 200 KB Guessed the password with 48 queries.
4 Correct 1 ms 200 KB Guessed the password with 89 queries.
5 Correct 1 ms 200 KB Guessed the password with 91 queries.
6 Correct 2 ms 200 KB Guessed the password with 177 queries.
7 Correct 29 ms 304 KB Guessed the password with 2749 queries.
8 Correct 37 ms 312 KB Guessed the password with 5070 queries.
9 Correct 42 ms 564 KB Guessed the password with 4586 queries.
10 Correct 78 ms 348 KB Guessed the password with 8083 queries.
11 Correct 78 ms 452 KB Guessed the password with 8160 queries.
12 Correct 92 ms 464 KB Guessed the password with 8159 queries.
13 Correct 106 ms 476 KB Guessed the password with 11501 queries.
14 Correct 107 ms 352 KB Guessed the password with 11601 queries.
15 Correct 122 ms 460 KB Guessed the password with 10880 queries.
16 Correct 119 ms 320 KB Guessed the password with 10860 queries.
17 Correct 119 ms 348 KB Guessed the password with 10210 queries.
18 Correct 100 ms 556 KB Guessed the password with 10248 queries.
19 Correct 104 ms 424 KB Guessed the password with 9684 queries.
20 Correct 92 ms 444 KB Guessed the password with 9776 queries.
21 Correct 110 ms 544 KB Guessed the password with 11643 queries.
22 Correct 127 ms 556 KB Guessed the password with 11712 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 56 queries.
2 Correct 2 ms 200 KB Guessed the password with 104 queries.
3 Correct 1 ms 200 KB Guessed the password with 48 queries.
4 Correct 1 ms 200 KB Guessed the password with 89 queries.
5 Correct 1 ms 200 KB Guessed the password with 91 queries.
6 Correct 2 ms 200 KB Guessed the password with 177 queries.
7 Correct 29 ms 304 KB Guessed the password with 2749 queries.
8 Correct 37 ms 312 KB Guessed the password with 5070 queries.
9 Correct 42 ms 564 KB Guessed the password with 4586 queries.
10 Correct 78 ms 348 KB Guessed the password with 8083 queries.
11 Correct 78 ms 452 KB Guessed the password with 8160 queries.
12 Correct 92 ms 464 KB Guessed the password with 8159 queries.
13 Correct 106 ms 476 KB Guessed the password with 11501 queries.
14 Correct 107 ms 352 KB Guessed the password with 11601 queries.
15 Correct 122 ms 460 KB Guessed the password with 10880 queries.
16 Correct 119 ms 320 KB Guessed the password with 10860 queries.
17 Correct 119 ms 348 KB Guessed the password with 10210 queries.
18 Correct 100 ms 556 KB Guessed the password with 10248 queries.
19 Correct 104 ms 424 KB Guessed the password with 9684 queries.
20 Correct 92 ms 444 KB Guessed the password with 9776 queries.
21 Correct 110 ms 544 KB Guessed the password with 11643 queries.
22 Correct 127 ms 556 KB Guessed the password with 11712 queries.
23 Correct 227 ms 460 KB Guessed the password with 23647 queries.
24 Correct 200 ms 532 KB Guessed the password with 20964 queries.
25 Correct 263 ms 380 KB Guessed the password with 23668 queries.
26 Correct 179 ms 704 KB Guessed the password with 19097 queries.
27 Correct 230 ms 584 KB Guessed the password with 23720 queries.
28 Correct 118 ms 476 KB Guessed the password with 16822 queries.
29 Correct 238 ms 584 KB Guessed the password with 23706 queries.
30 Correct 78 ms 484 KB Guessed the password with 14392 queries.