oj.uz

Submission #251384

# Submission time Handle Problem Language Result Execution time Memory
251384 2020-07-21T04:56:11 Z cheeheng Password (RMI18_password) C++14
80 / 100
 634 ms 628 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string q);

int p[28] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27};

string guess(int n, int s){
    int cnt[28];
    for(char i = 'a'; i < 'a'+s; i ++){
        string temp = "";
        for(int j = 0; j < n; j ++){
            temp += i;
        }
        cnt[i-'a'] = query(temp);
    }

    random_shuffle(p, p+s);

    string temp = "";
    int cntMatch = 0;
    for(int i = 0; i < s; i ++){
        int indx = 0;
        int j = 0;
        while(j < cnt[p[i]]){
            string temp2 = temp;
            if(indx == 0){
                temp2 = (char)('a'+p[i]) + temp;
            }else{
                temp2 = temp2.substr(0, indx) + (char)('a'+p[i]) + temp2.substr(indx);
            }
            //printf("%d: %s %s\n", j, temp.c_str(), temp2.c_str());
            int res = query(temp2);
            if(res > cntMatch){
                temp = temp2;
                cntMatch = res;
                j ++;
            }
            indx ++;
        }
    }

    return temp;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 88 queries.
2 Correct 2 ms 256 KB Guessed the password with 170 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 72 queries.
2 Correct 3 ms 256 KB Guessed the password with 176 queries.
3 Correct 3 ms 256 KB Guessed the password with 181 queries.
4 Correct 4 ms 256 KB Guessed the password with 239 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 376 KB Guessed the password with 7232 queries.
2 Correct 143 ms 376 KB Guessed the password with 9942 queries.
3 Correct 130 ms 256 KB Guessed the password with 12835 queries.
4 Correct 305 ms 376 KB Guessed the password with 20645 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 88 queries.
2 Correct 2 ms 256 KB Guessed the password with 170 queries.
3 Correct 1 ms 256 KB Guessed the password with 72 queries.
4 Correct 3 ms 256 KB Guessed the password with 176 queries.
5 Correct 3 ms 256 KB Guessed the password with 181 queries.
6 Correct 4 ms 256 KB Guessed the password with 239 queries.
7 Correct 78 ms 376 KB Guessed the password with 7232 queries.
8 Correct 143 ms 376 KB Guessed the password with 9942 queries.
9 Correct 130 ms 256 KB Guessed the password with 12835 queries.
10 Correct 305 ms 376 KB Guessed the password with 20645 queries.
11 Correct 425 ms 380 KB Guessed the password with 33706 queries.
12 Correct 321 ms 384 KB Guessed the password with 29104 queries.
13 Correct 307 ms 504 KB Guessed the password with 37784 queries.
14 Correct 546 ms 504 KB Guessed the password with 39441 queries.
15 Correct 378 ms 628 KB Guessed the password with 39587 queries.
16 Correct 315 ms 504 KB Guessed the password with 29698 queries.
17 Correct 440 ms 512 KB Guessed the password with 34571 queries.
18 Correct 302 ms 376 KB Guessed the password with 31301 queries.
19 Correct 351 ms 500 KB Guessed the password with 38121 queries.
20 Correct 260 ms 504 KB Guessed the password with 27031 queries.
21 Correct 420 ms 388 KB Guessed the password with 38027 queries.
22 Correct 312 ms 504 KB Guessed the password with 28965 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 88 queries.
2 Correct 2 ms 256 KB Guessed the password with 170 queries.
3 Correct 1 ms 256 KB Guessed the password with 72 queries.
4 Correct 3 ms 256 KB Guessed the password with 176 queries.
5 Correct 3 ms 256 KB Guessed the password with 181 queries.
6 Correct 4 ms 256 KB Guessed the password with 239 queries.
7 Correct 78 ms 376 KB Guessed the password with 7232 queries.
8 Correct 143 ms 376 KB Guessed the password with 9942 queries.
9 Correct 130 ms 256 KB Guessed the password with 12835 queries.
10 Correct 305 ms 376 KB Guessed the password with 20645 queries.
11 Correct 425 ms 380 KB Guessed the password with 33706 queries.
12 Correct 321 ms 384 KB Guessed the password with 29104 queries.
13 Correct 307 ms 504 KB Guessed the password with 37784 queries.
14 Correct 546 ms 504 KB Guessed the password with 39441 queries.
15 Correct 378 ms 628 KB Guessed the password with 39587 queries.
16 Correct 315 ms 504 KB Guessed the password with 29698 queries.
17 Correct 440 ms 512 KB Guessed the password with 34571 queries.
18 Correct 302 ms 376 KB Guessed the password with 31301 queries.
19 Correct 351 ms 500 KB Guessed the password with 38121 queries.
20 Correct 260 ms 504 KB Guessed the password with 27031 queries.
21 Correct 420 ms 388 KB Guessed the password with 38027 queries.
22 Correct 312 ms 504 KB Guessed the password with 28965 queries.
23 Execution timed out 634 ms 512 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -