oj.uz

Submission #331252

# Submission time Handle Problem Language Result Execution time Memory
331252 2020-11-27T20:26:09 Z Peti Password (RMI18_password) C++14
100 / 100
 307 ms 940 KB 
#include <iostream>
#include <vector>

using namespace std;

int query(string str);

string merge_strings(string sa, string sb){
    if(sa.size() < sb.size())
        swap(sa, sb);

    int x = 0;
    for(int i = 0; i < sb.size(); i++){
        while(1){
            string q = sa;
            q.insert(q.begin()+x, sb[i]);
            if(query(q) == (int)q.size()){
                sa = q;
                break;
            }
            x++;
        }
        x++;
    }

    return sa;
}

string guess(int n, int s){
    vector<string> v(s);
    for(int i = 0; i < s; i++){
        char c = (char)((int)'a' + i);
        string q;
        q.assign(n, c);
        v[i].assign(query(q), c);
    }

    while(v.size() > 1){
        int x = 0;
        for(int i = 0; i < (int)v.size(); i += 2){
            if(i+1 < (int)v.size())
                v[x++] = merge_strings(v[i], v[i+1]);
            else
                v[x++] = v[i];
        }
        v.resize(x);
    }

    return v[0];
}

Compilation message

password.cpp: In function 'std::string merge_strings(std::string, std::string)':
password.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0; i < sb.size(); i++){
      |                    ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 68 queries.
2 Correct 2 ms 384 KB Guessed the password with 117 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 52 queries.
2 Correct 2 ms 376 KB Guessed the password with 116 queries.
3 Correct 2 ms 364 KB Guessed the password with 105 queries.
4 Correct 3 ms 364 KB Guessed the password with 199 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 492 KB Guessed the password with 3476 queries.
2 Correct 72 ms 512 KB Guessed the password with 5035 queries.
3 Correct 82 ms 748 KB Guessed the password with 6860 queries.
4 Correct 86 ms 636 KB Guessed the password with 9085 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 68 queries.
2 Correct 2 ms 384 KB Guessed the password with 117 queries.
3 Correct 1 ms 364 KB Guessed the password with 52 queries.
4 Correct 2 ms 376 KB Guessed the password with 116 queries.
5 Correct 2 ms 364 KB Guessed the password with 105 queries.
6 Correct 3 ms 364 KB Guessed the password with 199 queries.
7 Correct 47 ms 492 KB Guessed the password with 3476 queries.
8 Correct 72 ms 512 KB Guessed the password with 5035 queries.
9 Correct 82 ms 748 KB Guessed the password with 6860 queries.
10 Correct 86 ms 636 KB Guessed the password with 9085 queries.
11 Correct 124 ms 748 KB Guessed the password with 13618 queries.
12 Correct 101 ms 620 KB Guessed the password with 11106 queries.
13 Correct 179 ms 544 KB Guessed the password with 14714 queries.
14 Correct 121 ms 620 KB Guessed the password with 13508 queries.
15 Correct 167 ms 680 KB Guessed the password with 14845 queries.
16 Correct 122 ms 620 KB Guessed the password with 13554 queries.
17 Correct 157 ms 492 KB Guessed the password with 16243 queries.
18 Correct 106 ms 784 KB Guessed the password with 13786 queries.
19 Correct 196 ms 688 KB Guessed the password with 16679 queries.
20 Correct 136 ms 492 KB Guessed the password with 12443 queries.
21 Correct 177 ms 492 KB Guessed the password with 17172 queries.
22 Correct 172 ms 620 KB Guessed the password with 14683 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 68 queries.
2 Correct 2 ms 384 KB Guessed the password with 117 queries.
3 Correct 1 ms 364 KB Guessed the password with 52 queries.
4 Correct 2 ms 376 KB Guessed the password with 116 queries.
5 Correct 2 ms 364 KB Guessed the password with 105 queries.
6 Correct 3 ms 364 KB Guessed the password with 199 queries.
7 Correct 47 ms 492 KB Guessed the password with 3476 queries.
8 Correct 72 ms 512 KB Guessed the password with 5035 queries.
9 Correct 82 ms 748 KB Guessed the password with 6860 queries.
10 Correct 86 ms 636 KB Guessed the password with 9085 queries.
11 Correct 124 ms 748 KB Guessed the password with 13618 queries.
12 Correct 101 ms 620 KB Guessed the password with 11106 queries.
13 Correct 179 ms 544 KB Guessed the password with 14714 queries.
14 Correct 121 ms 620 KB Guessed the password with 13508 queries.
15 Correct 167 ms 680 KB Guessed the password with 14845 queries.
16 Correct 122 ms 620 KB Guessed the password with 13554 queries.
17 Correct 157 ms 492 KB Guessed the password with 16243 queries.
18 Correct 106 ms 784 KB Guessed the password with 13786 queries.
19 Correct 196 ms 688 KB Guessed the password with 16679 queries.
20 Correct 136 ms 492 KB Guessed the password with 12443 queries.
21 Correct 177 ms 492 KB Guessed the password with 17172 queries.
22 Correct 172 ms 620 KB Guessed the password with 14683 queries.
23 Correct 235 ms 804 KB Guessed the password with 24110 queries.
24 Correct 215 ms 696 KB Guessed the password with 22738 queries.
25 Correct 277 ms 932 KB Guessed the password with 24133 queries.
26 Correct 307 ms 816 KB Guessed the password with 24582 queries.
27 Correct 291 ms 784 KB Guessed the password with 24164 queries.
28 Correct 204 ms 940 KB Guessed the password with 23573 queries.
29 Correct 274 ms 584 KB Guessed the password with 24198 queries.
30 Correct 249 ms 928 KB Guessed the password with 22400 queries.