Submission #464164

#	Time	Username	Problem	Language	Result	Execution time	Memory
464164		Mamedov	Password (RMI18_password)	C++17	100 / 100	299 ms	548 KiB

password

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ui unsigned int
#define pii pair<int, int>
#define pis pair<int, string>
#define piii pair<int, pii>
#define pb push_back
#define f first
#define s second
#define oo (1ll << 60)

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int query(string str);

void combine(string &str, string &add) {   /// str is the smallest one, add is the second smallest
    int str_len = str.length();
    int add_len = add.length();
    vector<int>comesAfter(str_len + 2);
    comesAfter[0] = 0;
    comesAfter[str_len + 1] = add_len;
    int i = str_len;
    int j = add_len - 1;
    while(i >= 1) {
        while(j >= 0) {
            string ask = str.substr(0, i) + add.substr(j);
            if(query(ask) < ask.length()) {
                break;
            }
            --j;
        }
        comesAfter[i] = j + 1;
        --i;
    }
    for(int i = 0; i <= str_len; ++i) {
        for(int j = comesAfter[i]; j < comesAfter[i + 1]; ++j) {
            str.insert(str.begin() + i + j, add[j]);
        }
    }
}
string guess(int n, int s) {
    string str, add;
    priority_queue<pis, vector<pis>, greater<pis>>pq;
    for(int i = 0; i < s; ++i) {
        str = "";
        for(int j = 0; j < n; ++j) {
            str += ('a' + i);
        }
        int Count = query(str);
        if(Count) {
            pq.push({Count, str.substr(0, Count)});
        }
    }
    while(pq.size() > 1) {
        str = (pq.top()).s; pq.pop();
        add = (pq.top()).s; pq.pop();
        combine(str, add);
        pq.push({str.length(), str});
    }
    return (pq.top()).s;
}

Compilation message (stderr)

password.cpp: In function 'void combine(std::string&, std::string&)':
password.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             if(query(ask) < ask.length()) {
      |                ~~~~~~~~~~~^~~~~~~~~~~~~~

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