oj.uz

Submission #199690

# Submission time Handle Problem Language Result Execution time Memory
199690 2020-02-02T20:35:25 Z zoooma13 Password (RMI18_password) C++14
100 / 100
 357 ms 748 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string s);

string merge(string s ,string t){
    for(int j=(int)s.size(),i=(int)t.size()-1; ~i; i--){
        while(true){
            string q = s;
            q.insert(q.begin()+j ,t[i]);
            if(query(q) == q.size()){
                s = q;
                break;
            }
            j--;
        }
    }
    return s;
}

string guess(int n ,int s){
    vector <string> vs;
    for(int x,i=0; i<s; i++){
        x = query(string(n ,'a'+i));
        if(x)
            vs.push_back(string(x ,'a'+i));
    }

    while(vs.size()>1){
        sort(vs.begin() ,vs.end() ,[](string s ,string t){
            return s.size() > t.size();
        });

        string x = vs.back(); vs.pop_back();
        string y = vs.back(); vs.pop_back();
        vs.push_back(merge(x ,y));
    }

    return vs.front();
}

Compilation message

password.cpp: In function 'std::__cxx11::string merge(std::__cxx11::string, std::__cxx11::string)':
password.cpp:11:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(query(q) == q.size()){
                ~~~~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Guessed the password with 67 queries.
2 Correct 7 ms 376 KB Guessed the password with 113 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Guessed the password with 52 queries.
2 Correct 6 ms 248 KB Guessed the password with 95 queries.
3 Correct 6 ms 376 KB Guessed the password with 105 queries.
4 Correct 7 ms 248 KB Guessed the password with 180 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 304 KB Guessed the password with 2771 queries.
2 Correct 90 ms 248 KB Guessed the password with 5093 queries.
3 Correct 65 ms 376 KB Guessed the password with 4598 queries.
4 Correct 88 ms 380 KB Guessed the password with 8151 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Guessed the password with 67 queries.
2 Correct 7 ms 376 KB Guessed the password with 113 queries.
3 Correct 6 ms 376 KB Guessed the password with 52 queries.
4 Correct 6 ms 248 KB Guessed the password with 95 queries.
5 Correct 6 ms 376 KB Guessed the password with 105 queries.
6 Correct 7 ms 248 KB Guessed the password with 180 queries.
7 Correct 43 ms 304 KB Guessed the password with 2771 queries.
8 Correct 90 ms 248 KB Guessed the password with 5093 queries.
9 Correct 65 ms 376 KB Guessed the password with 4598 queries.
10 Correct 88 ms 380 KB Guessed the password with 8151 queries.
11 Correct 84 ms 376 KB Guessed the password with 8185 queries.
12 Correct 121 ms 336 KB Guessed the password with 8175 queries.
13 Correct 132 ms 336 KB Guessed the password with 11551 queries.
14 Correct 128 ms 376 KB Guessed the password with 11681 queries.
15 Correct 181 ms 376 KB Guessed the password with 10909 queries.
16 Correct 125 ms 512 KB Guessed the password with 10883 queries.
17 Correct 133 ms 504 KB Guessed the password with 10237 queries.
18 Correct 151 ms 504 KB Guessed the password with 10306 queries.
19 Correct 125 ms 380 KB Guessed the password with 9714 queries.
20 Correct 106 ms 632 KB Guessed the password with 9806 queries.
21 Correct 174 ms 504 KB Guessed the password with 11740 queries.
22 Correct 144 ms 456 KB Guessed the password with 11811 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Guessed the password with 67 queries.
2 Correct 7 ms 376 KB Guessed the password with 113 queries.
3 Correct 6 ms 376 KB Guessed the password with 52 queries.
4 Correct 6 ms 248 KB Guessed the password with 95 queries.
5 Correct 6 ms 376 KB Guessed the password with 105 queries.
6 Correct 7 ms 248 KB Guessed the password with 180 queries.
7 Correct 43 ms 304 KB Guessed the password with 2771 queries.
8 Correct 90 ms 248 KB Guessed the password with 5093 queries.
9 Correct 65 ms 376 KB Guessed the password with 4598 queries.
10 Correct 88 ms 380 KB Guessed the password with 8151 queries.
11 Correct 84 ms 376 KB Guessed the password with 8185 queries.
12 Correct 121 ms 336 KB Guessed the password with 8175 queries.
13 Correct 132 ms 336 KB Guessed the password with 11551 queries.
14 Correct 128 ms 376 KB Guessed the password with 11681 queries.
15 Correct 181 ms 376 KB Guessed the password with 10909 queries.
16 Correct 125 ms 512 KB Guessed the password with 10883 queries.
17 Correct 133 ms 504 KB Guessed the password with 10237 queries.
18 Correct 151 ms 504 KB Guessed the password with 10306 queries.
19 Correct 125 ms 380 KB Guessed the password with 9714 queries.
20 Correct 106 ms 632 KB Guessed the password with 9806 queries.
21 Correct 174 ms 504 KB Guessed the password with 11740 queries.
22 Correct 144 ms 456 KB Guessed the password with 11811 queries.
23 Correct 324 ms 608 KB Guessed the password with 23737 queries.
24 Correct 280 ms 604 KB Guessed the password with 20994 queries.
25 Correct 357 ms 400 KB Guessed the password with 23745 queries.
26 Correct 253 ms 748 KB Guessed the password with 19151 queries.
27 Correct 276 ms 540 KB Guessed the password with 23758 queries.
28 Correct 208 ms 636 KB Guessed the password with 16845 queries.
29 Correct 298 ms 660 KB Guessed the password with 23735 queries.
30 Correct 231 ms 548 KB Guessed the password with 14414 queries.