oj.uz

Submission #318059

# Submission time Handle Problem Language Result Execution time Memory
318059 2020-10-31T11:29:45 Z nicolaalexandra Password (RMI18_password) C++14
100 / 100
 347 ms 932 KB 
#include <bits/stdc++.h>

using namespace std;

int query(string str);

priority_queue <pair<int,string> > h;
int f[30];

/*int query (string s){
    int ans;
    cout<<s<<"\n";
    cin>>ans;
    return ans;
}
*/

string guess (int n, int m){

    /// aflu frecventa fiecarui caracter
    int i,j;
    for (i=1;i<=m;i++){
        string v (n,i + 96);
        f[i] = query (v);

        string aux (f[i],i + 96);
        h.push(make_pair(-f[i],aux));
    }

    /// dau merge la toate sirurile sortate
    while (h.size() >= 2){
        int size1 = -h.top().first;
        string v = h.top().second;
        h.pop();

        int size2 = -h.top().first;
        string w = h.top().second;
        h.pop();

        string a = "";
        i = 0, j = 0;
        while (i < v.length() && j < w.length()){

            /// incerc sa pun v[i];
            string aux = a;
            aux.push_back(v[i]);
            /// acum completez cu celalalt sir
            for (int poz=j;poz<w.length();poz++)
                aux.push_back(w[poz]);

            if (query(aux) == aux.length()){
                a.push_back(v[i]);
                i++;
            } else {
                a.push_back(w[j]);
                j++;
            }

        }

        for (;i<v.length();i++)
            a.push_back(v[i]);
        for (;j<w.length();j++)
            a.push_back(w[j]);

        h.push(make_pair(-(size1+size2),a));
    }

    return h.top().second;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while (i < v.length() && j < w.length()){
      |                ~~^~~~~~~~~~~~
password.cpp:42:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while (i < v.length() && j < w.length()){
      |                                  ~~^~~~~~~~~~~~
password.cpp:48:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for (int poz=j;poz<w.length();poz++)
      |                            ~~~^~~~~~~~~~~
password.cpp:51:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if (query(aux) == aux.length()){
      |                 ~~~~~~~~~~~^~~~~~~~~~~~~~~
password.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (;i<v.length();i++)
      |               ~^~~~~~~~~~~
password.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (;j<w.length();j++)
      |               ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 57 queries.
2 Correct 3 ms 364 KB Guessed the password with 103 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 49 queries.
2 Correct 2 ms 364 KB Guessed the password with 90 queries.
3 Correct 1 ms 364 KB Guessed the password with 92 queries.
4 Correct 2 ms 364 KB Guessed the password with 178 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 364 KB Guessed the password with 2750 queries.
2 Correct 59 ms 484 KB Guessed the password with 5070 queries.
3 Correct 54 ms 484 KB Guessed the password with 4586 queries.
4 Correct 88 ms 484 KB Guessed the password with 8085 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 57 queries.
2 Correct 3 ms 364 KB Guessed the password with 103 queries.
3 Correct 1 ms 364 KB Guessed the password with 49 queries.
4 Correct 2 ms 364 KB Guessed the password with 90 queries.
5 Correct 1 ms 364 KB Guessed the password with 92 queries.
6 Correct 2 ms 364 KB Guessed the password with 178 queries.
7 Correct 31 ms 364 KB Guessed the password with 2750 queries.
8 Correct 59 ms 484 KB Guessed the password with 5070 queries.
9 Correct 54 ms 484 KB Guessed the password with 4586 queries.
10 Correct 88 ms 484 KB Guessed the password with 8085 queries.
11 Correct 98 ms 612 KB Guessed the password with 8154 queries.
12 Correct 107 ms 484 KB Guessed the password with 8162 queries.
13 Correct 137 ms 740 KB Guessed the password with 11500 queries.
14 Correct 122 ms 740 KB Guessed the password with 11602 queries.
15 Correct 119 ms 568 KB Guessed the password with 10878 queries.
16 Correct 112 ms 656 KB Guessed the password with 10862 queries.
17 Correct 125 ms 612 KB Guessed the password with 10209 queries.
18 Correct 140 ms 616 KB Guessed the password with 10245 queries.
19 Correct 141 ms 928 KB Guessed the password with 9687 queries.
20 Correct 134 ms 692 KB Guessed the password with 9778 queries.
21 Correct 157 ms 612 KB Guessed the password with 11641 queries.
22 Correct 151 ms 612 KB Guessed the password with 11708 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 57 queries.
2 Correct 3 ms 364 KB Guessed the password with 103 queries.
3 Correct 1 ms 364 KB Guessed the password with 49 queries.
4 Correct 2 ms 364 KB Guessed the password with 90 queries.
5 Correct 1 ms 364 KB Guessed the password with 92 queries.
6 Correct 2 ms 364 KB Guessed the password with 178 queries.
7 Correct 31 ms 364 KB Guessed the password with 2750 queries.
8 Correct 59 ms 484 KB Guessed the password with 5070 queries.
9 Correct 54 ms 484 KB Guessed the password with 4586 queries.
10 Correct 88 ms 484 KB Guessed the password with 8085 queries.
11 Correct 98 ms 612 KB Guessed the password with 8154 queries.
12 Correct 107 ms 484 KB Guessed the password with 8162 queries.
13 Correct 137 ms 740 KB Guessed the password with 11500 queries.
14 Correct 122 ms 740 KB Guessed the password with 11602 queries.
15 Correct 119 ms 568 KB Guessed the password with 10878 queries.
16 Correct 112 ms 656 KB Guessed the password with 10862 queries.
17 Correct 125 ms 612 KB Guessed the password with 10209 queries.
18 Correct 140 ms 616 KB Guessed the password with 10245 queries.
19 Correct 141 ms 928 KB Guessed the password with 9687 queries.
20 Correct 134 ms 692 KB Guessed the password with 9778 queries.
21 Correct 157 ms 612 KB Guessed the password with 11641 queries.
22 Correct 151 ms 612 KB Guessed the password with 11708 queries.
23 Correct 305 ms 788 KB Guessed the password with 23635 queries.
24 Correct 308 ms 500 KB Guessed the password with 20965 queries.
25 Correct 322 ms 692 KB Guessed the password with 23669 queries.
26 Correct 269 ms 932 KB Guessed the password with 19099 queries.
27 Correct 347 ms 836 KB Guessed the password with 23720 queries.
28 Correct 250 ms 632 KB Guessed the password with 16821 queries.
29 Correct 326 ms 736 KB Guessed the password with 23713 queries.
30 Correct 224 ms 776 KB Guessed the password with 14390 queries.