oj.uz

답안 #557383

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557383 2022-05-05T08:59:50 Z FatihSolak Password (RMI18_password) C++17
50 / 100
 1780 ms 166196 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;
// }
unordered_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] = myquery(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(myquery(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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 208 KB Guessed the password with 86 queries.
2 Correct 2 ms 296 KB Guessed the password with 154 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Guessed the password with 27 queries.
2 Correct 1 ms 208 KB Guessed the password with 103 queries.
3 Correct 1 ms 300 KB Guessed the password with 17 queries.
4 Correct 2 ms 320 KB Guessed the password with 133 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 4232 KB Guessed the password with 3770 queries.
2 Correct 220 ms 12868 KB Guessed the password with 9261 queries.
3 Correct 309 ms 16476 KB Guessed the password with 9839 queries.
4 Correct 645 ms 37764 KB Guessed the password with 18313 queries.

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 208 KB Guessed the password with 86 queries.
2 Correct 2 ms 296 KB Guessed the password with 154 queries.
3 Correct 1 ms 208 KB Guessed the password with 27 queries.
4 Correct 1 ms 208 KB Guessed the password with 103 queries.
5 Correct 1 ms 300 KB Guessed the password with 17 queries.
6 Correct 2 ms 320 KB Guessed the password with 133 queries.
7 Correct 91 ms 4232 KB Guessed the password with 3770 queries.
8 Correct 220 ms 12868 KB Guessed the password with 9261 queries.
9 Correct 309 ms 16476 KB Guessed the password with 9839 queries.
10 Correct 645 ms 37764 KB Guessed the password with 18313 queries.
11 Correct 1077 ms 94120 KB Guessed the password with 33171 queries.
12 Correct 1018 ms 25792 KB Guessed the password with 9059 queries.
13 Correct 1718 ms 140372 KB Guessed the password with 46117 queries.
14 Correct 1463 ms 54620 KB Guessed the password with 17880 queries.
15 Correct 1780 ms 140624 KB Guessed the password with 43506 queries.
16 Correct 1553 ms 52592 KB Guessed the password with 16258 queries.
17 Incorrect 1667 ms 166196 KB Could not guess the password with 50000 queries.
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 208 KB Guessed the password with 86 queries.
2 Correct 2 ms 296 KB Guessed the password with 154 queries.
3 Correct 1 ms 208 KB Guessed the password with 27 queries.
4 Correct 1 ms 208 KB Guessed the password with 103 queries.
5 Correct 1 ms 300 KB Guessed the password with 17 queries.
6 Correct 2 ms 320 KB Guessed the password with 133 queries.
7 Correct 91 ms 4232 KB Guessed the password with 3770 queries.
8 Correct 220 ms 12868 KB Guessed the password with 9261 queries.
9 Correct 309 ms 16476 KB Guessed the password with 9839 queries.
10 Correct 645 ms 37764 KB Guessed the password with 18313 queries.
11 Correct 1077 ms 94120 KB Guessed the password with 33171 queries.
12 Correct 1018 ms 25792 KB Guessed the password with 9059 queries.
13 Correct 1718 ms 140372 KB Guessed the password with 46117 queries.
14 Correct 1463 ms 54620 KB Guessed the password with 17880 queries.
15 Correct 1780 ms 140624 KB Guessed the password with 43506 queries.
16 Correct 1553 ms 52592 KB Guessed the password with 16258 queries.
17 Incorrect 1667 ms 166196 KB Could not guess the password with 50000 queries.
18 Halted 0 ms 0 KB -