oj.uz

Submission #261070

# Submission time Handle Problem Language Result Execution time Memory
261070 2020-08-11T10:59:42 Z handlename Password (RMI18_password) C++17
100 / 100
 533 ms 768 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair

int query(string str);
int num[26];
string guess(int n,int s){
    set<pair<int,string> > process;
    for (int i=0;i<s;i++){
        string cur;
        for (int j=0;j<n;j++) cur.pb('a'+i);
        num[i]=query(cur);
        cur.clear();
        for (int j=0;j<num[i];j++){
            cur.pb('a'+i);
        }
        process.insert(mp(num[i],cur));
    }
    while (process.size()>1){
        string one=(*(process.begin())).second;
        process.erase(process.begin());
        string two=(*(process.begin())).second;
        process.erase(process.begin());
        string res=two;
        int id=0; //idth guy not fixed
        for (int i=0;i<one.size();i++){
            string cur=res;
            while (true){
                string lol;
                for (int j=0;j<id;j++){
                    lol.pb(cur[j]);
                }
                lol.pb(one[i]);
                for (int j=id;j<cur.size();j++){
                    lol.pb(cur[j]);
                }
                if (query(lol)==lol.size()){
                    cur=lol;
                    break;
                }
                id++;
            }
            id++;
            res=cur;
        }
        process.insert(mp(res.size(),res));
    }
    return (*(process.begin())).second;
}

Compilation message

password.cpp: In function 'std::__cxx11::string guess(int, int)':
password.cpp:27:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<one.size();i++){
                      ~^~~~~~~~~~~
password.cpp:35:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j=id;j<cur.size();j++){
                               ~^~~~~~~~~~~
password.cpp:38:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (query(lol)==lol.size()){
                     ~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 69 queries.
2 Correct 1 ms 384 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 52 queries.
2 Correct 2 ms 256 KB Guessed the password with 92 queries.
3 Correct 2 ms 256 KB Guessed the password with 105 queries.
4 Correct 3 ms 256 KB Guessed the password with 179 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 256 KB Guessed the password with 2764 queries.
2 Correct 71 ms 372 KB Guessed the password with 5079 queries.
3 Correct 62 ms 376 KB Guessed the password with 4592 queries.
4 Correct 124 ms 376 KB Guessed the password with 8147 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 69 queries.
2 Correct 1 ms 384 KB Guessed the password with 111 queries.
3 Correct 1 ms 256 KB Guessed the password with 52 queries.
4 Correct 2 ms 256 KB Guessed the password with 92 queries.
5 Correct 2 ms 256 KB Guessed the password with 105 queries.
6 Correct 3 ms 256 KB Guessed the password with 179 queries.
7 Correct 46 ms 256 KB Guessed the password with 2764 queries.
8 Correct 71 ms 372 KB Guessed the password with 5079 queries.
9 Correct 62 ms 376 KB Guessed the password with 4592 queries.
10 Correct 124 ms 376 KB Guessed the password with 8147 queries.
11 Correct 146 ms 632 KB Guessed the password with 8174 queries.
12 Correct 158 ms 516 KB Guessed the password with 8176 queries.
13 Correct 207 ms 504 KB Guessed the password with 11521 queries.
14 Correct 210 ms 512 KB Guessed the password with 11625 queries.
15 Correct 208 ms 632 KB Guessed the password with 10894 queries.
16 Correct 213 ms 504 KB Guessed the password with 10882 queries.
17 Correct 198 ms 376 KB Guessed the password with 10226 queries.
18 Correct 202 ms 504 KB Guessed the password with 10292 queries.
19 Correct 194 ms 504 KB Guessed the password with 9704 queries.
20 Correct 222 ms 636 KB Guessed the password with 9794 queries.
21 Correct 223 ms 504 KB Guessed the password with 11694 queries.
22 Correct 246 ms 384 KB Guessed the password with 11776 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 69 queries.
2 Correct 1 ms 384 KB Guessed the password with 111 queries.
3 Correct 1 ms 256 KB Guessed the password with 52 queries.
4 Correct 2 ms 256 KB Guessed the password with 92 queries.
5 Correct 2 ms 256 KB Guessed the password with 105 queries.
6 Correct 3 ms 256 KB Guessed the password with 179 queries.
7 Correct 46 ms 256 KB Guessed the password with 2764 queries.
8 Correct 71 ms 372 KB Guessed the password with 5079 queries.
9 Correct 62 ms 376 KB Guessed the password with 4592 queries.
10 Correct 124 ms 376 KB Guessed the password with 8147 queries.
11 Correct 146 ms 632 KB Guessed the password with 8174 queries.
12 Correct 158 ms 516 KB Guessed the password with 8176 queries.
13 Correct 207 ms 504 KB Guessed the password with 11521 queries.
14 Correct 210 ms 512 KB Guessed the password with 11625 queries.
15 Correct 208 ms 632 KB Guessed the password with 10894 queries.
16 Correct 213 ms 504 KB Guessed the password with 10882 queries.
17 Correct 198 ms 376 KB Guessed the password with 10226 queries.
18 Correct 202 ms 504 KB Guessed the password with 10292 queries.
19 Correct 194 ms 504 KB Guessed the password with 9704 queries.
20 Correct 222 ms 636 KB Guessed the password with 9794 queries.
21 Correct 223 ms 504 KB Guessed the password with 11694 queries.
22 Correct 246 ms 384 KB Guessed the password with 11776 queries.
23 Correct 489 ms 656 KB Guessed the password with 23728 queries.
24 Correct 508 ms 660 KB Guessed the password with 20992 queries.
25 Correct 533 ms 528 KB Guessed the password with 23694 queries.
26 Correct 455 ms 736 KB Guessed the password with 19164 queries.
27 Correct 511 ms 640 KB Guessed the password with 23773 queries.
28 Correct 454 ms 768 KB Guessed the password with 16842 queries.
29 Correct 503 ms 416 KB Guessed the password with 23733 queries.
30 Correct 369 ms 436 KB Guessed the password with 14402 queries.