oj.uz

Submission #251385

# Submission time Handle Problem Language Result Execution time Memory
251385 2020-07-21T04:58:24 Z cheeheng Password (RMI18_password) C++14
80 / 100
 544 ms 632 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);
    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 68 queries.
2 Correct 2 ms 256 KB Guessed the password with 171 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 78 queries.
2 Correct 2 ms 256 KB Guessed the password with 164 queries.
3 Correct 1 ms 256 KB Guessed the password with 103 queries.
4 Correct 3 ms 256 KB Guessed the password with 239 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 256 KB Guessed the password with 6429 queries.
2 Correct 115 ms 376 KB Guessed the password with 10071 queries.
3 Correct 147 ms 504 KB Guessed the password with 12149 queries.
4 Correct 222 ms 504 KB Guessed the password with 20344 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 68 queries.
2 Correct 2 ms 256 KB Guessed the password with 171 queries.
3 Correct 1 ms 256 KB Guessed the password with 78 queries.
4 Correct 2 ms 256 KB Guessed the password with 164 queries.
5 Correct 1 ms 256 KB Guessed the password with 103 queries.
6 Correct 3 ms 256 KB Guessed the password with 239 queries.
7 Correct 91 ms 256 KB Guessed the password with 6429 queries.
8 Correct 115 ms 376 KB Guessed the password with 10071 queries.
9 Correct 147 ms 504 KB Guessed the password with 12149 queries.
10 Correct 222 ms 504 KB Guessed the password with 20344 queries.
11 Correct 433 ms 504 KB Guessed the password with 36561 queries.
12 Correct 228 ms 508 KB Guessed the password with 22129 queries.
13 Correct 416 ms 384 KB Guessed the password with 40845 queries.
14 Correct 337 ms 384 KB Guessed the password with 36112 queries.
15 Correct 421 ms 508 KB Guessed the password with 40180 queries.
16 Correct 355 ms 508 KB Guessed the password with 27322 queries.
17 Correct 427 ms 504 KB Guessed the password with 35219 queries.
18 Correct 302 ms 504 KB Guessed the password with 30582 queries.
19 Correct 454 ms 380 KB Guessed the password with 40415 queries.
20 Correct 315 ms 384 KB Guessed the password with 25765 queries.
21 Correct 466 ms 632 KB Guessed the password with 37803 queries.
22 Correct 407 ms 380 KB Guessed the password with 28508 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 68 queries.
2 Correct 2 ms 256 KB Guessed the password with 171 queries.
3 Correct 1 ms 256 KB Guessed the password with 78 queries.
4 Correct 2 ms 256 KB Guessed the password with 164 queries.
5 Correct 1 ms 256 KB Guessed the password with 103 queries.
6 Correct 3 ms 256 KB Guessed the password with 239 queries.
7 Correct 91 ms 256 KB Guessed the password with 6429 queries.
8 Correct 115 ms 376 KB Guessed the password with 10071 queries.
9 Correct 147 ms 504 KB Guessed the password with 12149 queries.
10 Correct 222 ms 504 KB Guessed the password with 20344 queries.
11 Correct 433 ms 504 KB Guessed the password with 36561 queries.
12 Correct 228 ms 508 KB Guessed the password with 22129 queries.
13 Correct 416 ms 384 KB Guessed the password with 40845 queries.
14 Correct 337 ms 384 KB Guessed the password with 36112 queries.
15 Correct 421 ms 508 KB Guessed the password with 40180 queries.
16 Correct 355 ms 508 KB Guessed the password with 27322 queries.
17 Correct 427 ms 504 KB Guessed the password with 35219 queries.
18 Correct 302 ms 504 KB Guessed the password with 30582 queries.
19 Correct 454 ms 380 KB Guessed the password with 40415 queries.
20 Correct 315 ms 384 KB Guessed the password with 25765 queries.
21 Correct 466 ms 632 KB Guessed the password with 37803 queries.
22 Correct 407 ms 380 KB Guessed the password with 28508 queries.
23 Incorrect 544 ms 488 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -