oj.uz

Submission #646264

# Submission time Handle Problem Language Result Execution time Memory
646264 2022-09-29T10:45:18 Z Matteo_Verz Password (RMI18_password) C++17
50 / 100
 377 ms 492 KB 
#include <bits/stdc++.h>
#ifdef BLAT
    #include "debug/debug.hpp"
#else
    #define debug(x...)
#endif

using namespace std;

int query(string s);

string mergeStrings(string &a, string &b) {
    string mergedSoFar, queryString;
    while (a.size() || b.size()) {
        if (!a.size()) {
            mergedSoFar += b;
            return mergedSoFar;
        }

        queryString = mergedSoFar + a[0] + b;
        int len = query(queryString);
        
        if (len == queryString.size()) {
            mergedSoFar.push_back(a[0]);
            a.erase(0, 1);
        } else {
            mergedSoFar.push_back(b[0]);
            b.erase(0, 1);
        }
    }

    return mergedSoFar;
}

string guess(int n, int s) {
    string ask;
    vector <string> vs;

    for (char ch = 'a'; ch - 'a' < s; ch++) {
        ask.clear();
        for (int i = 0; i < n; i++)
            ask += ch;
        int len = query(ask);

        ask = "";
        for (int i = 0; i < len; i++)
            ask += ch;
        vs.push_back(ask);
    }

    while (vs.size() > 1) {
        string a = vs.back();
        vs.pop_back();
        string b = vs.back();
        vs.pop_back();

        string c = mergeStrings(a, b);
        vs.push_back(c);
    }

    return vs[0];
}

Compilation message

password.cpp: In function 'std::string mergeStrings(std::string&, std::string&)':
password.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if (len == queryString.size()) {
      |             ~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 133 queries.
2 Correct 4 ms 208 KB Guessed the password with 295 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 48 queries.
2 Correct 2 ms 208 KB Guessed the password with 90 queries.
3 Correct 2 ms 208 KB Guessed the password with 171 queries.
4 Correct 3 ms 208 KB Guessed the password with 242 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 456 KB Guessed the password with 8039 queries.
2 Correct 110 ms 492 KB Guessed the password with 9973 queries.
3 Correct 107 ms 488 KB Guessed the password with 15998 queries.
4 Correct 177 ms 372 KB Guessed the password with 20973 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 133 queries.
2 Correct 4 ms 208 KB Guessed the password with 295 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 90 queries.
5 Correct 2 ms 208 KB Guessed the password with 171 queries.
6 Correct 3 ms 208 KB Guessed the password with 242 queries.
7 Correct 51 ms 456 KB Guessed the password with 8039 queries.
8 Correct 110 ms 492 KB Guessed the password with 9973 queries.
9 Correct 107 ms 488 KB Guessed the password with 15998 queries.
10 Correct 177 ms 372 KB Guessed the password with 20973 queries.
11 Correct 111 ms 384 KB Guessed the password with 12774 queries.
12 Incorrect 377 ms 456 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 133 queries.
2 Correct 4 ms 208 KB Guessed the password with 295 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 90 queries.
5 Correct 2 ms 208 KB Guessed the password with 171 queries.
6 Correct 3 ms 208 KB Guessed the password with 242 queries.
7 Correct 51 ms 456 KB Guessed the password with 8039 queries.
8 Correct 110 ms 492 KB Guessed the password with 9973 queries.
9 Correct 107 ms 488 KB Guessed the password with 15998 queries.
10 Correct 177 ms 372 KB Guessed the password with 20973 queries.
11 Correct 111 ms 384 KB Guessed the password with 12774 queries.
12 Incorrect 377 ms 456 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -