oj.uz

Submission #918913

# Submission time Handle Problem Language Result Execution time Memory
918913 2024-01-30T18:06:48 Z AtabayRajabli Password (RMI18_password) C++17
100 / 100
 131 ms 2000 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string s);

string join(string x, string y)
{
    int i = x.size();
    int j = y.size() - 1;

    string res = "";
    
    while(i > 0)
    {
        while(j >= 0)
        {
            string q = x.substr(0, i) + y.substr(j);
            if(query(q) == q.size())
            {
                res += y[j--];
            }
            else break;
        }
        res += x[i - 1];
        i--;
    }

    while(j >= 0)
        res += y[j--];

    reverse(res.begin(), res.end());

    return res;
}

string guess(int n, int s)
{
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> pq;
    for(int i = 0 ; i < s; i++)
    {
        string x = "";
        for(int j = 0; j < n; j++)
            x += char('a' + i);

        int cnt = query(x);
        x.clear();
        
        while(cnt--)
            x += char('a' + i);
        
        if(cnt)pq.push({x.size(), x});
    }

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

        string r = join(a, b);
        pq.push({r.size(), r});
    }

    return pq.top().second;
}

Compilation message

password.cpp: In function 'std::string join(std::string, std::string)':
password.cpp:18:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |             if(query(q) == q.size())
      |                ~~~~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 59 queries.
2 Correct 1 ms 436 KB Guessed the password with 100 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 48 queries.
2 Correct 1 ms 344 KB Guessed the password with 92 queries.
3 Correct 0 ms 344 KB Guessed the password with 18 queries.
4 Correct 1 ms 344 KB Guessed the password with 175 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 696 KB Guessed the password with 2758 queries.
2 Correct 19 ms 692 KB Guessed the password with 5083 queries.
3 Correct 18 ms 696 KB Guessed the password with 4586 queries.
4 Correct 37 ms 724 KB Guessed the password with 8128 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 59 queries.
2 Correct 1 ms 436 KB Guessed the password with 100 queries.
3 Correct 1 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 92 queries.
5 Correct 0 ms 344 KB Guessed the password with 18 queries.
6 Correct 1 ms 344 KB Guessed the password with 175 queries.
7 Correct 11 ms 696 KB Guessed the password with 2758 queries.
8 Correct 19 ms 692 KB Guessed the password with 5083 queries.
9 Correct 18 ms 696 KB Guessed the password with 4586 queries.
10 Correct 37 ms 724 KB Guessed the password with 8128 queries.
11 Correct 36 ms 732 KB Guessed the password with 8154 queries.
12 Correct 39 ms 732 KB Guessed the password with 8162 queries.
13 Correct 51 ms 752 KB Guessed the password with 11520 queries.
14 Correct 50 ms 1460 KB Guessed the password with 11656 queries.
15 Correct 60 ms 716 KB Guessed the password with 10875 queries.
16 Correct 51 ms 948 KB Guessed the password with 10858 queries.
17 Correct 42 ms 740 KB Guessed the password with 10218 queries.
18 Correct 45 ms 736 KB Guessed the password with 10244 queries.
19 Correct 51 ms 996 KB Guessed the password with 9687 queries.
20 Correct 44 ms 736 KB Guessed the password with 9781 queries.
21 Correct 55 ms 1240 KB Guessed the password with 11726 queries.
22 Correct 57 ms 1200 KB Guessed the password with 11782 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 59 queries.
2 Correct 1 ms 436 KB Guessed the password with 100 queries.
3 Correct 1 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 92 queries.
5 Correct 0 ms 344 KB Guessed the password with 18 queries.
6 Correct 1 ms 344 KB Guessed the password with 175 queries.
7 Correct 11 ms 696 KB Guessed the password with 2758 queries.
8 Correct 19 ms 692 KB Guessed the password with 5083 queries.
9 Correct 18 ms 696 KB Guessed the password with 4586 queries.
10 Correct 37 ms 724 KB Guessed the password with 8128 queries.
11 Correct 36 ms 732 KB Guessed the password with 8154 queries.
12 Correct 39 ms 732 KB Guessed the password with 8162 queries.
13 Correct 51 ms 752 KB Guessed the password with 11520 queries.
14 Correct 50 ms 1460 KB Guessed the password with 11656 queries.
15 Correct 60 ms 716 KB Guessed the password with 10875 queries.
16 Correct 51 ms 948 KB Guessed the password with 10858 queries.
17 Correct 42 ms 740 KB Guessed the password with 10218 queries.
18 Correct 45 ms 736 KB Guessed the password with 10244 queries.
19 Correct 51 ms 996 KB Guessed the password with 9687 queries.
20 Correct 44 ms 736 KB Guessed the password with 9781 queries.
21 Correct 55 ms 1240 KB Guessed the password with 11726 queries.
22 Correct 57 ms 1200 KB Guessed the password with 11782 queries.
23 Correct 107 ms 2000 KB Guessed the password with 23693 queries.
24 Correct 99 ms 1268 KB Guessed the password with 20947 queries.
25 Correct 122 ms 1012 KB Guessed the password with 23705 queries.
26 Correct 89 ms 1280 KB Guessed the password with 19107 queries.
27 Correct 104 ms 1248 KB Guessed the password with 23733 queries.
28 Correct 77 ms 1240 KB Guessed the password with 16828 queries.
29 Correct 131 ms 1264 KB Guessed the password with 23694 queries.
30 Correct 64 ms 756 KB Guessed the password with 14391 queries.