Submission #696286

#	Time	Username	Problem	Language	Result	Execution time	Memory
696286		jhwest2	Password (RMI18_password)	C++17	80 / 100	1043 ms	644 KiB

password

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

int query(string str);

int n, s, cnt[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);
    }
    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 ask = left;
        int sz = left.size();
        vector<int> num(sz + 1);
        for (int j = 0; j <= sz; j++) {
            string tmp = ask;
            while (tmp.size() < n)
                tmp += 'a' + i;
            num[j] = query(tmp) - ask.size();
            if (j != sz)
                ask.pop_back();
        }
        ask = left;
        left.clear();
        for (int j = sz; j > 0; j--) 
            num[j] -= num[j - 1];
        for (int j = 0; j <= sz; j++) {
            while (num[sz - j]--)
                left += 'a' + i;
            if (j != sz)
                left += ask[j];
        }
    }
    for (int i = s / 2 + 1; i < s; i++) {
        string ask = right;
        int sz = right.size();
        vector<int> num(sz + 1);

        for (int j = 0; j <= sz; j++) {
            string tmp = ask;
            while (tmp.size() < n)
                tmp += 'a' + i;
            num[j] = query(tmp) - ask.size();
            if (j != sz)
                ask.pop_back();
        }
        ask = right;
        right.clear();
        for (int j = sz; j > 0; j--) 
            num[j] -= num[j - 1];
        for (int j = 0; j <= sz; j++) {
            while (num[sz - j]--)
                right += 'a' + i;
            if (j != sz)
                right += ask[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:28:31: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |             while (tmp.size() < n)
      |                    ~~~~~~~~~~~^~~
password.cpp:52:31: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |             while (tmp.size() < n)
      |                    ~~~~~~~~~~~^~~
password.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < right.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
password.cpp:72:73: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         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