oj.uz

Submission #918915

# Submission time Handle Problem Language Result Execution time Memory
918915 2024-01-30T18:08:01 Z vjudge1 Password (RMI18_password) C++17
100 / 100
 124 ms 1480 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 12 ms 952 KB Guessed the password with 2758 queries.
2 Correct 37 ms 672 KB Guessed the password with 5083 queries.
3 Correct 19 ms 964 KB Guessed the password with 4586 queries.
4 Correct 36 ms 1188 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 12 ms 952 KB Guessed the password with 2758 queries.
8 Correct 37 ms 672 KB Guessed the password with 5083 queries.
9 Correct 19 ms 964 KB Guessed the password with 4586 queries.
10 Correct 36 ms 1188 KB Guessed the password with 8128 queries.
11 Correct 37 ms 720 KB Guessed the password with 8154 queries.
12 Correct 34 ms 680 KB Guessed the password with 8162 queries.
13 Correct 55 ms 1480 KB Guessed the password with 11520 queries.
14 Correct 53 ms 968 KB Guessed the password with 11656 queries.
15 Correct 48 ms 720 KB Guessed the password with 10875 queries.
16 Correct 48 ms 1224 KB Guessed the password with 10858 queries.
17 Correct 45 ms 968 KB Guessed the password with 10218 queries.
18 Correct 47 ms 1224 KB Guessed the password with 10244 queries.
19 Correct 45 ms 1216 KB Guessed the password with 9687 queries.
20 Correct 49 ms 744 KB Guessed the password with 9781 queries.
21 Correct 54 ms 972 KB Guessed the password with 11726 queries.
22 Correct 55 ms 712 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 12 ms 952 KB Guessed the password with 2758 queries.
8 Correct 37 ms 672 KB Guessed the password with 5083 queries.
9 Correct 19 ms 964 KB Guessed the password with 4586 queries.
10 Correct 36 ms 1188 KB Guessed the password with 8128 queries.
11 Correct 37 ms 720 KB Guessed the password with 8154 queries.
12 Correct 34 ms 680 KB Guessed the password with 8162 queries.
13 Correct 55 ms 1480 KB Guessed the password with 11520 queries.
14 Correct 53 ms 968 KB Guessed the password with 11656 queries.
15 Correct 48 ms 720 KB Guessed the password with 10875 queries.
16 Correct 48 ms 1224 KB Guessed the password with 10858 queries.
17 Correct 45 ms 968 KB Guessed the password with 10218 queries.
18 Correct 47 ms 1224 KB Guessed the password with 10244 queries.
19 Correct 45 ms 1216 KB Guessed the password with 9687 queries.
20 Correct 49 ms 744 KB Guessed the password with 9781 queries.
21 Correct 54 ms 972 KB Guessed the password with 11726 queries.
22 Correct 55 ms 712 KB Guessed the password with 11782 queries.
23 Correct 103 ms 1260 KB Guessed the password with 23693 queries.
24 Correct 94 ms 1248 KB Guessed the password with 20947 queries.
25 Correct 109 ms 1280 KB Guessed the password with 23705 queries.
26 Correct 86 ms 992 KB Guessed the password with 19107 queries.
27 Correct 124 ms 1004 KB Guessed the password with 23733 queries.
28 Correct 82 ms 1020 KB Guessed the password with 16828 queries.
29 Correct 112 ms 1004 KB Guessed the password with 23694 queries.
30 Correct 68 ms 860 KB Guessed the password with 14391 queries.