oj.uz

Submission #557381

# Submission time Handle Problem Language Result Execution time Memory
557381 2022-05-05T08:57:59 Z FatihSolak Password (RMI18_password) C++17
50 / 100
 1352 ms 292 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;
// }
map<string,int> mp;
int myquery(string s){
    if(mp.count(s))return mp[s];
    return mp[s] = query(s);
}
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:44:30: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |             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 208 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 2 ms 208 KB Guessed the password with 137 queries.
3 Correct 1 ms 208 KB Guessed the password with 18 queries.
4 Correct 3 ms 208 KB Guessed the password with 295 queries.

Subtask #3
20.0 / 20.0

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