oj.uz

Submission #251370

# Submission time Handle Problem Language Result Execution time Memory
251370 2020-07-21T04:24:39 Z dwsc Password (RMI18_password) C++14
100 / 100
 929 ms 760 KB 
#include <bits/stdc++.h>
using namespace std;
int query(string str);
vector<string> mergevector(vector<string> v){
    vector<string> newvector;
    for (int i = 0; i < v.size(); i+= 2){
        if (i == v.size()-1){
            newvector.push_back(v[i]);
            break;
        }
        string s1 = v[i],s2 = v[i+1];
        //cout << s1 << " " << s2 << "hi\n";
        string newstring = s1;
        int insertionpos = 0;
        int curpos = 0;
        while (curpos < s2.length()){
            string temp = "";
            for (int j = 0; j < newstring.length(); j++){
                if (j == insertionpos) temp += s2[curpos];
                temp += newstring[j];
            }
            if (insertionpos == newstring.length()) temp += s2[curpos];
            if (query(temp) == temp.length()){
                newstring = temp;
                curpos++;
                insertionpos++;
            }
            else{
                insertionpos++;
            }
        }
        //cout << newstring << "\n";
        newvector.push_back(newstring);
    }
    return newvector;
}
string guess(int n, int s){
    vector<string> letters;
    for (int i = 0; i < s; i++){
        int ans = 0;
        char c = (char)(i+97);
        string act = "";
        for (int j = 1; j <= n; j++){
            string temp = act+c;
            if (query(temp) == ans) break;
            act = temp;
            ans++;
        }
        //cout << act << "\n";
        if (ans) letters.push_back(act);
    }
    while (letters.size() > 1)letters = mergevector(letters);
    return letters[0];
}

Compilation message

password.cpp: In function 'std::vector<std::__cxx11::basic_string<char> > mergevector(std::vector<std::__cxx11::basic_string<char> >)':
password.cpp:6:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i+= 2){
                     ~~^~~~~~~~~~
password.cpp:7:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == v.size()-1){
             ~~^~~~~~~~~~~~~
password.cpp:16:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (curpos < s2.length()){
                ~~~~~~~^~~~~~~~~~~~~
password.cpp:18:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < newstring.length(); j++){
                             ~~^~~~~~~~~~~~~~~~~~~~
password.cpp:22:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (insertionpos == newstring.length()) temp += s2[curpos];
                 ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
password.cpp:23:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (query(temp) == temp.length()){
                 ~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 98 queries.
2 Correct 2 ms 256 KB Guessed the password with 186 queries.
3 Correct 3 ms 256 KB Guessed the password with 183 queries.
4 Correct 3 ms 256 KB Guessed the password with 303 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 256 KB Guessed the password with 4553 queries.
2 Correct 118 ms 376 KB Guessed the password with 6353 queries.
3 Correct 172 ms 376 KB Guessed the password with 8641 queries.
4 Correct 224 ms 384 KB Guessed the password with 11099 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 83 queries.
2 Correct 2 ms 256 KB Guessed the password with 140 queries.
3 Correct 1 ms 256 KB Guessed the password with 98 queries.
4 Correct 2 ms 256 KB Guessed the password with 186 queries.
5 Correct 3 ms 256 KB Guessed the password with 183 queries.
6 Correct 3 ms 256 KB Guessed the password with 303 queries.
7 Correct 65 ms 256 KB Guessed the password with 4553 queries.
8 Correct 118 ms 376 KB Guessed the password with 6353 queries.
9 Correct 172 ms 376 KB Guessed the password with 8641 queries.
10 Correct 224 ms 384 KB Guessed the password with 11099 queries.
11 Correct 357 ms 640 KB Guessed the password with 16464 queries.
12 Correct 264 ms 376 KB Guessed the password with 14012 queries.
13 Correct 332 ms 380 KB Guessed the password with 17761 queries.
14 Correct 305 ms 384 KB Guessed the password with 16528 queries.
15 Correct 328 ms 376 KB Guessed the password with 18158 queries.
16 Correct 335 ms 376 KB Guessed the password with 16772 queries.
17 Correct 671 ms 392 KB Guessed the password with 19559 queries.
18 Correct 407 ms 508 KB Guessed the password with 17292 queries.
19 Correct 508 ms 632 KB Guessed the password with 20157 queries.
20 Correct 297 ms 504 KB Guessed the password with 17257 queries.
21 Correct 480 ms 520 KB Guessed the password with 20756 queries.
22 Correct 439 ms 404 KB Guessed the password with 18231 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 83 queries.
2 Correct 2 ms 256 KB Guessed the password with 140 queries.
3 Correct 1 ms 256 KB Guessed the password with 98 queries.
4 Correct 2 ms 256 KB Guessed the password with 186 queries.
5 Correct 3 ms 256 KB Guessed the password with 183 queries.
6 Correct 3 ms 256 KB Guessed the password with 303 queries.
7 Correct 65 ms 256 KB Guessed the password with 4553 queries.
8 Correct 118 ms 376 KB Guessed the password with 6353 queries.
9 Correct 172 ms 376 KB Guessed the password with 8641 queries.
10 Correct 224 ms 384 KB Guessed the password with 11099 queries.
11 Correct 357 ms 640 KB Guessed the password with 16464 queries.
12 Correct 264 ms 376 KB Guessed the password with 14012 queries.
13 Correct 332 ms 380 KB Guessed the password with 17761 queries.
14 Correct 305 ms 384 KB Guessed the password with 16528 queries.
15 Correct 328 ms 376 KB Guessed the password with 18158 queries.
16 Correct 335 ms 376 KB Guessed the password with 16772 queries.
17 Correct 671 ms 392 KB Guessed the password with 19559 queries.
18 Correct 407 ms 508 KB Guessed the password with 17292 queries.
19 Correct 508 ms 632 KB Guessed the password with 20157 queries.
20 Correct 297 ms 504 KB Guessed the password with 17257 queries.
21 Correct 480 ms 520 KB Guessed the password with 20756 queries.
22 Correct 439 ms 404 KB Guessed the password with 18231 queries.
23 Correct 550 ms 660 KB Guessed the password with 29113 queries.
24 Correct 530 ms 760 KB Guessed the password with 28056 queries.
25 Correct 627 ms 532 KB Guessed the password with 29182 queries.
26 Correct 779 ms 656 KB Guessed the password with 29670 queries.
27 Correct 679 ms 516 KB Guessed the password with 29171 queries.
28 Correct 664 ms 520 KB Guessed the password with 28810 queries.
29 Correct 797 ms 624 KB Guessed the password with 29208 queries.
30 Correct 929 ms 416 KB Guessed the password with 29029 queries.