oj.uz

답안 #557380

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -