oj.uz

Submission #646330

# Submission time Handle Problem Language Result Execution time Memory
646330 2022-09-29T14:39:39 Z Matteo_Verz Password (RMI18_password) C++17
100 / 100
 292 ms 624 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;
}

struct Compare {
    bool operator()(const string &a, const string &b) {
        if (a.size() == b.size())
            return a > b;
        return a.size() > b.size();
    }
};

string guess(int n, int s) {
    string ask;
    priority_queue <string, vector <string>, Compare> pq;

    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;
        pq.push(ask);
    }

    while (pq.size() > 1) {
        string a = pq.top();
        pq.pop();
        string b = pq.top();
        pq.pop();

        debug(a, b);

        string c = mergeStrings(a, b);
        debug(c);
        pq.push(c);
    }

    return pq.top();
}

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 1 ms 208 KB Guessed the password with 69 queries.
2 Correct 1 ms 208 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 496 KB Guessed the password with 2764 queries.
2 Correct 53 ms 336 KB Guessed the password with 5079 queries.
3 Correct 48 ms 360 KB Guessed the password with 4592 queries.
4 Correct 80 ms 312 KB Guessed the password with 8147 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 69 queries.
2 Correct 1 ms 208 KB Guessed the password with 111 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 2 ms 208 KB Guessed the password with 92 queries.
5 Correct 1 ms 208 KB Guessed the password with 105 queries.
6 Correct 2 ms 208 KB Guessed the password with 179 queries.
7 Correct 34 ms 496 KB Guessed the password with 2764 queries.
8 Correct 53 ms 336 KB Guessed the password with 5079 queries.
9 Correct 48 ms 360 KB Guessed the password with 4592 queries.
10 Correct 80 ms 312 KB Guessed the password with 8147 queries.
11 Correct 83 ms 624 KB Guessed the password with 8174 queries.
12 Correct 93 ms 500 KB Guessed the password with 8176 queries.
13 Correct 128 ms 388 KB Guessed the password with 11521 queries.
14 Correct 119 ms 380 KB Guessed the password with 11625 queries.
15 Correct 131 ms 376 KB Guessed the password with 10894 queries.
16 Correct 126 ms 376 KB Guessed the password with 10882 queries.
17 Correct 142 ms 448 KB Guessed the password with 10226 queries.
18 Correct 81 ms 388 KB Guessed the password with 10292 queries.
19 Correct 90 ms 396 KB Guessed the password with 9704 queries.
20 Correct 116 ms 512 KB Guessed the password with 9794 queries.
21 Correct 96 ms 396 KB Guessed the password with 11694 queries.
22 Correct 108 ms 396 KB Guessed the password with 11776 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 69 queries.
2 Correct 1 ms 208 KB Guessed the password with 111 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 2 ms 208 KB Guessed the password with 92 queries.
5 Correct 1 ms 208 KB Guessed the password with 105 queries.
6 Correct 2 ms 208 KB Guessed the password with 179 queries.
7 Correct 34 ms 496 KB Guessed the password with 2764 queries.
8 Correct 53 ms 336 KB Guessed the password with 5079 queries.
9 Correct 48 ms 360 KB Guessed the password with 4592 queries.
10 Correct 80 ms 312 KB Guessed the password with 8147 queries.
11 Correct 83 ms 624 KB Guessed the password with 8174 queries.
12 Correct 93 ms 500 KB Guessed the password with 8176 queries.
13 Correct 128 ms 388 KB Guessed the password with 11521 queries.
14 Correct 119 ms 380 KB Guessed the password with 11625 queries.
15 Correct 131 ms 376 KB Guessed the password with 10894 queries.
16 Correct 126 ms 376 KB Guessed the password with 10882 queries.
17 Correct 142 ms 448 KB Guessed the password with 10226 queries.
18 Correct 81 ms 388 KB Guessed the password with 10292 queries.
19 Correct 90 ms 396 KB Guessed the password with 9704 queries.
20 Correct 116 ms 512 KB Guessed the password with 9794 queries.
21 Correct 96 ms 396 KB Guessed the password with 11694 queries.
22 Correct 108 ms 396 KB Guessed the password with 11776 queries.
23 Correct 198 ms 440 KB Guessed the password with 23728 queries.
24 Correct 261 ms 408 KB Guessed the password with 20992 queries.
25 Correct 292 ms 516 KB Guessed the password with 23694 queries.
26 Correct 247 ms 420 KB Guessed the password with 19164 queries.
27 Correct 274 ms 496 KB Guessed the password with 23773 queries.
28 Correct 172 ms 508 KB Guessed the password with 16842 queries.
29 Correct 159 ms 416 KB Guessed the password with 23733 queries.
30 Correct 161 ms 412 KB Guessed the password with 14402 queries.