oj.uz

Submission #1117080

# Submission time Handle Problem Language Result Execution time Memory
1117080 2024-11-22T20:02:45 Z Bula Password (RMI18_password) C++17
100 / 100
 504 ms 1628 KB 
#include<bits/stdc++.h>
using namespace std;
int query(string p);
string guess(int n, int s){
    string t;
    set<pair<int, string>> st;
    for(char c = 'a'; c <= 'a' + s - 1; c++){
        string p;
        for(int i = 0; i < n; i++) p += c;
        int x = query(p);
        if(x == 0) continue;
        p.clear();
        for(int i = 0; i < x; i++) p += c;
        st.insert({p.size(), p});
    }
    while(st.size() > 1){
      pair<int, string> pr = *st.begin();
      st.erase(st.begin());
      string a = pr.second;
      pr = *st.begin();
      st.erase(st.begin());
      string b = pr.second, ans;
      while(a.size() > 0){
        string p = ans;
        p += a[0]; p += b;
        if(query(p) == p.size()){
          ans += a[0];
          a.erase(a.begin());
        }else{
          ans += b[0];
          b.erase(b.begin());
        }
      }
      ans += b;
      st.insert({ans.size(), ans});
    }
    pair<int, string> pr = *st.begin();
    return pr.second;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 69 queries.
2 Correct 3 ms 336 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 52 queries.
2 Correct 3 ms 336 KB Guessed the password with 92 queries.
3 Correct 3 ms 436 KB Guessed the password with 105 queries.
4 Correct 4 ms 444 KB Guessed the password with 179 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 704 KB Guessed the password with 2764 queries.
2 Correct 102 ms 988 KB Guessed the password with 5079 queries.
3 Correct 98 ms 708 KB Guessed the password with 4592 queries.
4 Correct 164 ms 1220 KB Guessed the password with 8147 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 69 queries.
2 Correct 3 ms 336 KB Guessed the password with 111 queries.
3 Correct 2 ms 336 KB Guessed the password with 52 queries.
4 Correct 3 ms 336 KB Guessed the password with 92 queries.
5 Correct 3 ms 436 KB Guessed the password with 105 queries.
6 Correct 4 ms 444 KB Guessed the password with 179 queries.
7 Correct 41 ms 704 KB Guessed the password with 2764 queries.
8 Correct 102 ms 988 KB Guessed the password with 5079 queries.
9 Correct 98 ms 708 KB Guessed the password with 4592 queries.
10 Correct 164 ms 1220 KB Guessed the password with 8147 queries.
11 Correct 182 ms 1000 KB Guessed the password with 8174 queries.
12 Correct 154 ms 996 KB Guessed the password with 8176 queries.
13 Correct 240 ms 760 KB Guessed the password with 11521 queries.
14 Correct 244 ms 768 KB Guessed the password with 11625 queries.
15 Correct 224 ms 764 KB Guessed the password with 10894 queries.
16 Correct 211 ms 996 KB Guessed the password with 10882 queries.
17 Correct 201 ms 1008 KB Guessed the password with 10226 queries.
18 Correct 215 ms 500 KB Guessed the password with 10292 queries.
19 Correct 196 ms 728 KB Guessed the password with 9704 queries.
20 Correct 197 ms 756 KB Guessed the password with 9794 queries.
21 Correct 261 ms 1012 KB Guessed the password with 11694 queries.
22 Correct 269 ms 712 KB Guessed the password with 11776 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 69 queries.
2 Correct 3 ms 336 KB Guessed the password with 111 queries.
3 Correct 2 ms 336 KB Guessed the password with 52 queries.
4 Correct 3 ms 336 KB Guessed the password with 92 queries.
5 Correct 3 ms 436 KB Guessed the password with 105 queries.
6 Correct 4 ms 444 KB Guessed the password with 179 queries.
7 Correct 41 ms 704 KB Guessed the password with 2764 queries.
8 Correct 102 ms 988 KB Guessed the password with 5079 queries.
9 Correct 98 ms 708 KB Guessed the password with 4592 queries.
10 Correct 164 ms 1220 KB Guessed the password with 8147 queries.
11 Correct 182 ms 1000 KB Guessed the password with 8174 queries.
12 Correct 154 ms 996 KB Guessed the password with 8176 queries.
13 Correct 240 ms 760 KB Guessed the password with 11521 queries.
14 Correct 244 ms 768 KB Guessed the password with 11625 queries.
15 Correct 224 ms 764 KB Guessed the password with 10894 queries.
16 Correct 211 ms 996 KB Guessed the password with 10882 queries.
17 Correct 201 ms 1008 KB Guessed the password with 10226 queries.
18 Correct 215 ms 500 KB Guessed the password with 10292 queries.
19 Correct 196 ms 728 KB Guessed the password with 9704 queries.
20 Correct 197 ms 756 KB Guessed the password with 9794 queries.
21 Correct 261 ms 1012 KB Guessed the password with 11694 queries.
22 Correct 269 ms 712 KB Guessed the password with 11776 queries.
23 Correct 490 ms 1060 KB Guessed the password with 23728 queries.
24 Correct 451 ms 1048 KB Guessed the password with 20992 queries.
25 Correct 448 ms 884 KB Guessed the password with 23694 queries.
26 Correct 404 ms 1004 KB Guessed the password with 19164 queries.
27 Correct 504 ms 1272 KB Guessed the password with 23773 queries.
28 Correct 360 ms 1628 KB Guessed the password with 16842 queries.
29 Correct 502 ms 1092 KB Guessed the password with 23733 queries.
30 Correct 294 ms 1524 KB Guessed the password with 14402 queries.