Submission #696295

#	Time	Username	Problem	Language	Result	Execution time	Memory
696295		jhwest2	Password (RMI18_password)	C++14	100 / 100	516 ms	644 KiB

password

#include <bits/stdc++.h>
using namespace std;

int query(string str);

int n, s, cnt[26], num[5050], w[26];
string guess(int _n, int _s) {
    n = _n; s = _s;

    for (int i = 0; i < s; i++) {
        string str;
        for (int j = 0; j < n; j++)
            str += 'a' + i;
        cnt[i] = query(str);
    }
    for (int i = 0; i < s; i++)
        w[i] = i;

    sort(w, w + s, [&](auto i, auto j) {
        return cnt[i] < cnt[j];
        });

    string left, right;
    for (int i = 0; i < s / 2; i++) {
        string str;
        for (int j = 0; j < n; j++)
            str += 'a' + w[i];

        int sz = left.size();
        for (int j = 0; j <= sz; j++)
            num[j] = query(left.substr(0, sz - j) + str.substr(0, n - sz + j)) - sz + j;
        for (int j = sz; j > 0; j--) 
            num[j] -= num[j - 1];

        str = left;
        left.clear();
        for (int j = 0; j <= sz; j++) {
            while (num[sz - j]--)
                left += 'a' + w[i];
            if (j != sz)
                left += str[j];
        }
    }
    for (int i = s / 2; i < s; i++) {
        string str;
        for (int j = 0; j < n; j++)
            str += 'a' + w[i];

        int sz = right.size();
        for (int j = 0; j <= sz; j++)
            num[j] = query(right.substr(0, sz - j) + str.substr(0, n - sz + j)) - sz + j;
        for (int j = sz; j > 0; j--) 
            num[j] -= num[j - 1];

        str = right;
        right.clear();
        for (int j = 0; j <= sz; j++) {
            while (num[sz - j]--)
                right += 'a' + w[i];
            if (j != sz)
                right += str[j];
        }
    }
    string ans;
    int sz = left.size(), p = 0;
    for (int i = 0; i < right.size(); i++) {
        while (p < sz && query(ans + right[i] + left.substr(p, sz - p)) != ans.size() + 1 + sz - p) {
            ans += left[p++];
        }
        ans += right[i];        
    }
    while (p < sz)
        ans += left[p++];
    return ans;
}

Compilation message (stderr)

password.cpp: In function 'std::string guess(int, int)':
password.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < right.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
password.cpp:67:73: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         while (p < sz && query(ans + right[i] + left.substr(p, sz - p)) != ans.size() + 1 + sz - p) {
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20