oj.uz

Submission #251486

# Submission time Handle Problem Language Result Execution time Memory
251486 2020-07-21T12:31:18 Z cheeheng Password (RMI18_password) C++14
100 / 100
 338 ms 732 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string q);

int cnt[29];

string rec(int s, int e){
    //printf("rec(%d, %d)\n", s, e);
    if(s == e){
        string temp = "";
        for(int i = 0; i < cnt[s]; i ++){
            temp += (char)('a'+s);
        }
        return temp;
    }else{
        int m = (s+e)>>1;
        string str1 = rec(s, m);
        string str2 = rec(m+1, e);

        string res = "";
        int indx1 = 0;
        int indx2 = 0;

        int len1 = str1.size();
        int len2 = str2.size();
        while(indx1 < len1 || indx2 < len2){
            //printf("indx1=%d indx2=%d\n", indx1, indx2);
            if(indx1 == len1){
                res += str2[indx2++];
            }else if(indx2 == len2){
                res += str1[indx1++];
            }else{
                string temp = res + str1[indx1] + str2.substr(indx2, len2-indx2);
                int qres = query(temp);
                if(qres == (int)temp.size()){
                    res += str1[indx1++];
                }else{
                    res += str2[indx2++];
                }
            }
        }

        return res;
    }
}

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

    return rec(0, s-1);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 49 queries.
2 Correct 1 ms 256 KB Guessed the password with 117 queries.
3 Correct 1 ms 256 KB Guessed the password with 92 queries.
4 Correct 3 ms 256 KB Guessed the password with 197 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 384 KB Guessed the password with 3456 queries.
2 Correct 56 ms 368 KB Guessed the password with 5025 queries.
3 Correct 69 ms 496 KB Guessed the password with 6352 queries.
4 Correct 90 ms 504 KB Guessed the password with 8693 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 61 queries.
2 Correct 1 ms 256 KB Guessed the password with 101 queries.
3 Correct 1 ms 256 KB Guessed the password with 49 queries.
4 Correct 1 ms 256 KB Guessed the password with 117 queries.
5 Correct 1 ms 256 KB Guessed the password with 92 queries.
6 Correct 3 ms 256 KB Guessed the password with 197 queries.
7 Correct 38 ms 384 KB Guessed the password with 3456 queries.
8 Correct 56 ms 368 KB Guessed the password with 5025 queries.
9 Correct 69 ms 496 KB Guessed the password with 6352 queries.
10 Correct 90 ms 504 KB Guessed the password with 8693 queries.
11 Correct 131 ms 388 KB Guessed the password with 13638 queries.
12 Correct 147 ms 388 KB Guessed the password with 12459 queries.
13 Correct 147 ms 504 KB Guessed the password with 14392 queries.
14 Correct 135 ms 376 KB Guessed the password with 13937 queries.
15 Correct 134 ms 632 KB Guessed the password with 15073 queries.
16 Correct 117 ms 376 KB Guessed the password with 14154 queries.
17 Correct 184 ms 504 KB Guessed the password with 16054 queries.
18 Correct 165 ms 376 KB Guessed the password with 15189 queries.
19 Correct 172 ms 376 KB Guessed the password with 16410 queries.
20 Correct 143 ms 376 KB Guessed the password with 14247 queries.
21 Correct 156 ms 500 KB Guessed the password with 16849 queries.
22 Correct 178 ms 504 KB Guessed the password with 15315 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 61 queries.
2 Correct 1 ms 256 KB Guessed the password with 101 queries.
3 Correct 1 ms 256 KB Guessed the password with 49 queries.
4 Correct 1 ms 256 KB Guessed the password with 117 queries.
5 Correct 1 ms 256 KB Guessed the password with 92 queries.
6 Correct 3 ms 256 KB Guessed the password with 197 queries.
7 Correct 38 ms 384 KB Guessed the password with 3456 queries.
8 Correct 56 ms 368 KB Guessed the password with 5025 queries.
9 Correct 69 ms 496 KB Guessed the password with 6352 queries.
10 Correct 90 ms 504 KB Guessed the password with 8693 queries.
11 Correct 131 ms 388 KB Guessed the password with 13638 queries.
12 Correct 147 ms 388 KB Guessed the password with 12459 queries.
13 Correct 147 ms 504 KB Guessed the password with 14392 queries.
14 Correct 135 ms 376 KB Guessed the password with 13937 queries.
15 Correct 134 ms 632 KB Guessed the password with 15073 queries.
16 Correct 117 ms 376 KB Guessed the password with 14154 queries.
17 Correct 184 ms 504 KB Guessed the password with 16054 queries.
18 Correct 165 ms 376 KB Guessed the password with 15189 queries.
19 Correct 172 ms 376 KB Guessed the password with 16410 queries.
20 Correct 143 ms 376 KB Guessed the password with 14247 queries.
21 Correct 156 ms 500 KB Guessed the password with 16849 queries.
22 Correct 178 ms 504 KB Guessed the password with 15315 queries.
23 Correct 240 ms 732 KB Guessed the password with 23612 queries.
24 Correct 223 ms 432 KB Guessed the password with 22226 queries.
25 Correct 216 ms 408 KB Guessed the password with 23794 queries.
26 Correct 276 ms 528 KB Guessed the password with 23332 queries.
27 Correct 276 ms 540 KB Guessed the password with 23763 queries.
28 Correct 338 ms 540 KB Guessed the password with 23045 queries.
29 Correct 302 ms 640 KB Guessed the password with 23847 queries.
30 Correct 300 ms 412 KB Guessed the password with 22506 queries.