Submission #985851

#	Time	Username	Problem	Language	Result	Execution time	Memory
985851		boris_mihov	Password (RMI18_password)	C++17	100 / 100	440 ms	1968 KiB

password

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20