oj.uz

Submission #557380

# Submission time Handle Problem Language Result Execution time Memory
557380 2022-05-05T08:54:34 Z FatihSolak Password (RMI18_password) C++17
50 / 100
 1207 ms 304 KB 
#include <bits/stdc++.h>
using namespace std;
int query(string str);
// string password;
// int query(string q) {
//   int len = q.size();
//   int i = 0, j = 0, plen = password.size();
//   while (i < plen && j < len) {
//     while ((i < plen) && (password[i] != q[j])) {
//       i++;
//     }
//     if (i < plen) {
//       i++;
//       j++;
//     }
//   }
//   return j;
// }

string guess(int n, int s){
    vector<int> cnt(s);
    vector<int> used(s);
    for(int i = 0;i<s;i++){
        string tmp = "";
        for(int j = 0;j<n;j++)
            tmp += (char) (i + 'a');
        //cout << tmp << endl;
        cnt[i] = query(tmp);
    }
    string res = "";
    for(int x = n-1;x>=0;x--){
        int val = 0;
        while(cnt[val] == 0)
            val++;
        for(int i = val+1;i<s;i++){
            if(cnt[i] == 0)continue;
            string tmp = "";
            for(int j = 0;j<cnt[val];j++)
                tmp += (char) (val + 'a');
            while(tmp.size() < n)
                tmp += (char) (i + 'a');
            if(query(tmp) >= cnt[val] + used[i] + 1){
                val = i;
            }
        }
        res += (char)(val + 'a');
        used[val]++;
        cnt[val]--;
        //cout << res << endl;
    }
    reverse(res.begin(),res.end());
    return res;
}
// int main(){
//     #ifdef Local
//         freopen("in.txt","r",stdin);
//         freopen("out.txt","w",stdout);
//     #endif
//     int n,s;
//     cin >> n >> s;
//     cin >> password;
//     guess(n,s);
// }

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:40:30: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |             while(tmp.size() < n)
      |                   ~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 48 queries.
2 Correct 1 ms 208 KB Guessed the password with 137 queries.
3 Correct 1 ms 208 KB Guessed the password with 18 queries.
4 Correct 5 ms 208 KB Guessed the password with 295 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 304 KB Guessed the password with 9308 queries.
2 Correct 275 ms 284 KB Guessed the password with 17735 queries.
3 Correct 330 ms 288 KB Guessed the password with 20689 queries.
4 Correct 633 ms 288 KB Guessed the password with 37112 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 121 queries.
2 Correct 3 ms 292 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 1 ms 208 KB Guessed the password with 137 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 5 ms 208 KB Guessed the password with 295 queries.
7 Correct 126 ms 304 KB Guessed the password with 9308 queries.
8 Correct 275 ms 284 KB Guessed the password with 17735 queries.
9 Correct 330 ms 288 KB Guessed the password with 20689 queries.
10 Correct 633 ms 288 KB Guessed the password with 37112 queries.
11 Correct 997 ms 292 KB Guessed the password with 41055 queries.
12 Incorrect 1207 ms 288 KB Could not guess the password with 50000 queries.
13 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 121 queries.
2 Correct 3 ms 292 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 1 ms 208 KB Guessed the password with 137 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 5 ms 208 KB Guessed the password with 295 queries.
7 Correct 126 ms 304 KB Guessed the password with 9308 queries.
8 Correct 275 ms 284 KB Guessed the password with 17735 queries.
9 Correct 330 ms 288 KB Guessed the password with 20689 queries.
10 Correct 633 ms 288 KB Guessed the password with 37112 queries.
11 Correct 997 ms 292 KB Guessed the password with 41055 queries.
12 Incorrect 1207 ms 288 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -