oj.uz

Submission #248800

# Submission time Handle Problem Language Result Execution time Memory
248800 2020-07-13T12:32:52 Z tqbfjotld Password (RMI18_password) C++14
100 / 100
 416 ms 616 KB 
#include <bits/stdc++.h>
using namespace std;
int query(string str);

bool cmp(string s1, string s2){
    return s1.size()>s2.size();
}

priority_queue<string,vector<string>,function<bool(string,string)> > pq(cmp);

string repeat(char c, int n){
    string ret = "";
    for (int x = 0; x<n; x++){
        ret+=c;
    }
    return ret;
}

string guess(int n, int s){
    for (int x = 0; x<s; x++){
        string qu = repeat('a'+x,n);
        int t = query(qu);
        if (t!=0)pq.push(repeat('a'+x,t));
    }
    while (pq.size()>1){
        string s1 = pq.top(); pq.pop();
        string s2 = pq.top(); pq.pop();
        string nw = "";
        nw+=s2[0];
        int c1 = 0;
        int c2 = 1;
        while (nw.size()<s1.size()+s2.size()){
            string qu = nw+s1.substr(c1,s1.size());
            int t = query(qu);
            if (t==qu.size()){
                if (c2==s2.size()){
                    nw += s1.substr(c1,s1.size());
                }
                else{
                    nw += s2[c2];
                    c2++;
                }
            }
            else{
                nw.pop_back();
                c2--;
                nw += s1[c1];
                c1++;
            }
        }
        pq.push(nw);
    }
    return pq.top();
}

Compilation message

password.cpp: In function 'std::__cxx11::string guess(int, int)':
password.cpp:35:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (t==qu.size()){
                 ~^~~~~~~~~~~
password.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (c2==s2.size()){
                     ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.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 119 queries.
3 Correct 1 ms 256 KB Guessed the password with 91 queries.
4 Correct 4 ms 256 KB Guessed the password with 253 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 376 KB Guessed the password with 3976 queries.
2 Correct 63 ms 256 KB Guessed the password with 7455 queries.
3 Correct 59 ms 504 KB Guessed the password with 6629 queries.
4 Correct 121 ms 504 KB Guessed the password with 11707 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 74 queries.
2 Correct 2 ms 256 KB Guessed the password with 147 queries.
3 Correct 1 ms 256 KB Guessed the password with 68 queries.
4 Correct 2 ms 256 KB Guessed the password with 119 queries.
5 Correct 1 ms 256 KB Guessed the password with 91 queries.
6 Correct 4 ms 256 KB Guessed the password with 253 queries.
7 Correct 37 ms 376 KB Guessed the password with 3976 queries.
8 Correct 63 ms 256 KB Guessed the password with 7455 queries.
9 Correct 59 ms 504 KB Guessed the password with 6629 queries.
10 Correct 121 ms 504 KB Guessed the password with 11707 queries.
11 Correct 114 ms 384 KB Guessed the password with 11792 queries.
12 Correct 132 ms 256 KB Guessed the password with 11809 queries.
13 Correct 165 ms 384 KB Guessed the password with 16850 queries.
14 Correct 198 ms 384 KB Guessed the password with 16969 queries.
15 Correct 155 ms 384 KB Guessed the password with 15813 queries.
16 Correct 135 ms 384 KB Guessed the password with 15747 queries.
17 Correct 135 ms 384 KB Guessed the password with 14640 queries.
18 Correct 181 ms 384 KB Guessed the password with 14626 queries.
19 Correct 138 ms 384 KB Guessed the password with 14011 queries.
20 Correct 177 ms 384 KB Guessed the password with 14152 queries.
21 Correct 156 ms 384 KB Guessed the password with 16881 queries.
22 Correct 209 ms 504 KB Guessed the password with 16979 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 74 queries.
2 Correct 2 ms 256 KB Guessed the password with 147 queries.
3 Correct 1 ms 256 KB Guessed the password with 68 queries.
4 Correct 2 ms 256 KB Guessed the password with 119 queries.
5 Correct 1 ms 256 KB Guessed the password with 91 queries.
6 Correct 4 ms 256 KB Guessed the password with 253 queries.
7 Correct 37 ms 376 KB Guessed the password with 3976 queries.
8 Correct 63 ms 256 KB Guessed the password with 7455 queries.
9 Correct 59 ms 504 KB Guessed the password with 6629 queries.
10 Correct 121 ms 504 KB Guessed the password with 11707 queries.
11 Correct 114 ms 384 KB Guessed the password with 11792 queries.
12 Correct 132 ms 256 KB Guessed the password with 11809 queries.
13 Correct 165 ms 384 KB Guessed the password with 16850 queries.
14 Correct 198 ms 384 KB Guessed the password with 16969 queries.
15 Correct 155 ms 384 KB Guessed the password with 15813 queries.
16 Correct 135 ms 384 KB Guessed the password with 15747 queries.
17 Correct 135 ms 384 KB Guessed the password with 14640 queries.
18 Correct 181 ms 384 KB Guessed the password with 14626 queries.
19 Correct 138 ms 384 KB Guessed the password with 14011 queries.
20 Correct 177 ms 384 KB Guessed the password with 14152 queries.
21 Correct 156 ms 384 KB Guessed the password with 16881 queries.
22 Correct 209 ms 504 KB Guessed the password with 16979 queries.
23 Correct 318 ms 428 KB Guessed the password with 34662 queries.
24 Correct 363 ms 484 KB Guessed the password with 30457 queries.
25 Correct 416 ms 408 KB Guessed the password with 34639 queries.
26 Correct 300 ms 404 KB Guessed the password with 27813 queries.
27 Correct 413 ms 616 KB Guessed the password with 34606 queries.
28 Correct 254 ms 400 KB Guessed the password with 24371 queries.
29 Correct 359 ms 408 KB Guessed the password with 34625 queries.
30 Correct 256 ms 428 KB Guessed the password with 20810 queries.