Submission #199684

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
199684	2020-02-02T18:35:03 Z	Osama_Alkhodairy	Password (RMI18_password)	C++17	80 / 100	620 ms	632 KB

password

#include <bits/stdc++.h>
//~ #include "grader.cpp"
using namespace std;

int query(string s);
string guess(int n, int c){
    vector <int> f(c);
    for(char i = 'a' ; i < 'a' + c ; i++){
        f[i - 'a'] = query(string(n, i));
    }
    string ans;
    for(char i = 'a' ; i < 'a' + c ; i++){
        string cur = ans;
        for(int j = 0 ; j < f[i - 'a'] ; j++){
            int l = 0, r = ans.size();
            while(l <= r){
                int mid = (l + r) / 2;
                if(query(ans.substr(0, mid) + string(j + 1, i)) == mid + j + 1) l = mid + 1;
                else r = mid - 1;
            }
            cur.insert(cur.begin() + r, i);
        }
        ans = cur;
    }
    return ans;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	248 KB	Guessed the password with 61 queries.
2	Correct	6 ms	376 KB	Guessed the password with 102 queries.

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	376 KB	Guessed the password with 148 queries.
2	Correct	6 ms	376 KB	Guessed the password with 183 queries.
3	Correct	9 ms	256 KB	Guessed the password with 334 queries.
4	Correct	10 ms	376 KB	Guessed the password with 467 queries.

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	320 KB	Guessed the password with 7954 queries.
2	Correct	130 ms	504 KB	Guessed the password with 11163 queries.
3	Correct	140 ms	248 KB	Guessed the password with 13763 queries.
4	Correct	189 ms	248 KB	Guessed the password with 18558 queries.

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	248 KB	Guessed the password with 61 queries.
2	Correct	6 ms	376 KB	Guessed the password with 102 queries.
3	Correct	7 ms	376 KB	Guessed the password with 148 queries.
4	Correct	6 ms	376 KB	Guessed the password with 183 queries.
5	Correct	9 ms	256 KB	Guessed the password with 334 queries.
6	Correct	10 ms	376 KB	Guessed the password with 467 queries.
7	Correct	76 ms	320 KB	Guessed the password with 7954 queries.
8	Correct	130 ms	504 KB	Guessed the password with 11163 queries.
9	Correct	140 ms	248 KB	Guessed the password with 13763 queries.
10	Correct	189 ms	248 KB	Guessed the password with 18558 queries.
11	Correct	201 ms	376 KB	Guessed the password with 23329 queries.
12	Correct	282 ms	376 KB	Guessed the password with 27234 queries.
13	Correct	290 ms	376 KB	Guessed the password with 27895 queries.
14	Correct	285 ms	248 KB	Guessed the password with 29719 queries.
15	Correct	388 ms	376 KB	Guessed the password with 28965 queries.
16	Correct	434 ms	504 KB	Guessed the password with 31726 queries.
17	Correct	291 ms	632 KB	Guessed the password with 28928 queries.
18	Correct	376 ms	504 KB	Guessed the password with 32917 queries.
19	Correct	305 ms	508 KB	Guessed the password with 28595 queries.
20	Correct	361 ms	376 KB	Guessed the password with 33904 queries.
21	Correct	339 ms	504 KB	Guessed the password with 31824 queries.
22	Correct	289 ms	504 KB	Guessed the password with 35570 queries.

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	248 KB	Guessed the password with 61 queries.
2	Correct	6 ms	376 KB	Guessed the password with 102 queries.
3	Correct	7 ms	376 KB	Guessed the password with 148 queries.
4	Correct	6 ms	376 KB	Guessed the password with 183 queries.
5	Correct	9 ms	256 KB	Guessed the password with 334 queries.
6	Correct	10 ms	376 KB	Guessed the password with 467 queries.
7	Correct	76 ms	320 KB	Guessed the password with 7954 queries.
8	Correct	130 ms	504 KB	Guessed the password with 11163 queries.
9	Correct	140 ms	248 KB	Guessed the password with 13763 queries.
10	Correct	189 ms	248 KB	Guessed the password with 18558 queries.
11	Correct	201 ms	376 KB	Guessed the password with 23329 queries.
12	Correct	282 ms	376 KB	Guessed the password with 27234 queries.
13	Correct	290 ms	376 KB	Guessed the password with 27895 queries.
14	Correct	285 ms	248 KB	Guessed the password with 29719 queries.
15	Correct	388 ms	376 KB	Guessed the password with 28965 queries.
16	Correct	434 ms	504 KB	Guessed the password with 31726 queries.
17	Correct	291 ms	632 KB	Guessed the password with 28928 queries.
18	Correct	376 ms	504 KB	Guessed the password with 32917 queries.
19	Correct	305 ms	508 KB	Guessed the password with 28595 queries.
20	Correct	361 ms	376 KB	Guessed the password with 33904 queries.
21	Correct	339 ms	504 KB	Guessed the password with 31824 queries.
22	Correct	289 ms	504 KB	Guessed the password with 35570 queries.
23	Incorrect	620 ms	464 KB	Could not guess the password with 50000 queries.
24	Halted	0 ms	0 KB	-