Submission #696291

#	Time	Username	Problem	Language	Result	Execution time	Memory
696291		jhwest2	Password (RMI18_password)	C++14	80 / 100	581 ms	592 KiB

password

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

int query(string str);

int n, s, cnt[26], num[5050];
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);
    }
    string left, right;
    for (int i = 0; i < cnt[0]; i++)
        left += 'a';
    for (int i = 0; i < cnt[s / 2]; i++)
        right += 'a' + s / 2;

    for (int i = 1; i < s / 2; i++) {
        string str;
        for (int j = 0; j < n; j++)
            str += 'a' + 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' + i;
            if (j != sz)
                left += str[j];
        }
    }
    for (int i = s / 2 + 1; i < s; i++) {
        string str;
        for (int j = 0; j < n; j++)
            str += 'a' + 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' + 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:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < right.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
password.cpp:65:73: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         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: 0 / 20