oj.uz

Submission #985851

# Submission time Handle Problem Language Result Execution time Memory
985851 2024-05-19T06:45:46 Z boris_mihov Password (RMI18_password) C++17
100 / 100
 440 ms 1968 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

template <class T> void chkmax(T &a, T &b) {a = std::max(a, b);};
template <class T> void chkmin(T &a, T &b) {a = std::min(a, b);};
template <class T> void chkmax(T &a, T b) {a = std::max(a, b);};
template <class T> void chkmin(T &a, T b) {a = std::min(a, b);};

typedef long long llong;
const int ALPHABET = 26;
const int MAXN = 5000 + 10;
const int INF  = 1e9;

int query(std::string);

namespace
{
    int n, l;
}

int lens[ALPHABET];
int perm[ALPHABET];

std::string guess(int n, int l)
{
    ::n = n;
    ::l = l;

    for (int i = 0 ; i < l ; ++i)
    {
        std::string s(n, 'a' + i);
        lens[i] = query(s);
    }

    std::iota(perm, perm + l, 0);
    std::sort(perm, perm + l, [&](int x, int y)
    {
        return lens[x] < lens[y];
    });

    std::string ans(lens[perm[0]], 'a' + perm[0]);
    for (int i = 1 ; i < l ; ++i)
    {
        int last = -1;
        int idx = perm[i];
        std::vector <int> positions;
        for (int j = 0 ; j < lens[idx] ; ++j)
        {
            int l = last, r = ans.size() + 1, mid;
            while (l < r - 1)
            {
                mid = l + r >> 1;
                std::string toQuery = ans;
                while (toQuery.size() > mid) toQuery.pop_back();
                for (int k = 0 ; k < lens[idx] ; ++k)
                {
                    toQuery += char('a' + idx);
                }

                int res = query(toQuery);
                if (res == toQuery.size() - j) l = mid;
                else r = mid;
            }   

            positions.push_back(l);
            last = l;
        }

        for (int j = (int)positions.size() - 1 ; j >= 0 ; --j)
        {
            ans.insert(ans.begin() + positions[j], char('a' + idx));
        }
    }

    return ans;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:55:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |                 mid = l + r >> 1;
      |                       ~~^~~
password.cpp:57:39: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |                 while (toQuery.size() > mid) toQuery.pop_back();
      |                        ~~~~~~~~~~~~~~~^~~~~
password.cpp:64:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |                 if (res == toQuery.size() - j) l = mid;
      |                     ~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 60 queries.
2 Correct 1 ms 500 KB Guessed the password with 103 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 108 queries.
2 Correct 1 ms 344 KB Guessed the password with 181 queries.
3 Correct 1 ms 344 KB Guessed the password with 250 queries.
4 Correct 2 ms 596 KB Guessed the password with 314 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 952 KB Guessed the password with 6252 queries.
2 Correct 63 ms 956 KB Guessed the password with 9012 queries.
3 Correct 79 ms 952 KB Guessed the password with 11789 queries.
4 Correct 119 ms 708 KB Guessed the password with 15476 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 60 queries.
2 Correct 1 ms 500 KB Guessed the password with 103 queries.
3 Correct 1 ms 344 KB Guessed the password with 108 queries.
4 Correct 1 ms 344 KB Guessed the password with 181 queries.
5 Correct 1 ms 344 KB Guessed the password with 250 queries.
6 Correct 2 ms 596 KB Guessed the password with 314 queries.
7 Correct 39 ms 952 KB Guessed the password with 6252 queries.
8 Correct 63 ms 956 KB Guessed the password with 9012 queries.
9 Correct 79 ms 952 KB Guessed the password with 11789 queries.
10 Correct 119 ms 708 KB Guessed the password with 15476 queries.
11 Correct 191 ms 948 KB Guessed the password with 22896 queries.
12 Correct 173 ms 472 KB Guessed the password with 22885 queries.
13 Correct 204 ms 700 KB Guessed the password with 24927 queries.
14 Correct 189 ms 692 KB Guessed the password with 25051 queries.
15 Correct 222 ms 688 KB Guessed the password with 27061 queries.
16 Correct 215 ms 956 KB Guessed the password with 27231 queries.
17 Correct 224 ms 952 KB Guessed the password with 27474 queries.
18 Correct 228 ms 960 KB Guessed the password with 27376 queries.
19 Correct 251 ms 944 KB Guessed the password with 28513 queries.
20 Correct 238 ms 936 KB Guessed the password with 28248 queries.
21 Correct 236 ms 692 KB Guessed the password with 28648 queries.
22 Correct 296 ms 696 KB Guessed the password with 30758 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 60 queries.
2 Correct 1 ms 500 KB Guessed the password with 103 queries.
3 Correct 1 ms 344 KB Guessed the password with 108 queries.
4 Correct 1 ms 344 KB Guessed the password with 181 queries.
5 Correct 1 ms 344 KB Guessed the password with 250 queries.
6 Correct 2 ms 596 KB Guessed the password with 314 queries.
7 Correct 39 ms 952 KB Guessed the password with 6252 queries.
8 Correct 63 ms 956 KB Guessed the password with 9012 queries.
9 Correct 79 ms 952 KB Guessed the password with 11789 queries.
10 Correct 119 ms 708 KB Guessed the password with 15476 queries.
11 Correct 191 ms 948 KB Guessed the password with 22896 queries.
12 Correct 173 ms 472 KB Guessed the password with 22885 queries.
13 Correct 204 ms 700 KB Guessed the password with 24927 queries.
14 Correct 189 ms 692 KB Guessed the password with 25051 queries.
15 Correct 222 ms 688 KB Guessed the password with 27061 queries.
16 Correct 215 ms 956 KB Guessed the password with 27231 queries.
17 Correct 224 ms 952 KB Guessed the password with 27474 queries.
18 Correct 228 ms 960 KB Guessed the password with 27376 queries.
19 Correct 251 ms 944 KB Guessed the password with 28513 queries.
20 Correct 238 ms 936 KB Guessed the password with 28248 queries.
21 Correct 236 ms 692 KB Guessed the password with 28648 queries.
22 Correct 296 ms 696 KB Guessed the password with 30758 queries.
23 Correct 414 ms 1388 KB Guessed the password with 43482 queries.
24 Correct 415 ms 1696 KB Guessed the password with 43708 queries.
25 Correct 432 ms 1296 KB Guessed the password with 45194 queries.
26 Correct 440 ms 1220 KB Guessed the password with 44946 queries.
27 Correct 398 ms 1124 KB Guessed the password with 44893 queries.
28 Correct 397 ms 1968 KB Guessed the password with 44337 queries.
29 Correct 440 ms 1564 KB Guessed the password with 46173 queries.
30 Correct 421 ms 1544 KB Guessed the password with 44719 queries.