Submission #478181

#	Time	Username	Problem	Language	Result	Execution time	Memory
478181		Alexandruabcde	Password (RMI18_password)	C++14	100 / 100	417 ms	652 KiB

password

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 5005;
constexpr int SMAX = 27;
typedef pair<int, string> PIS;

int query(string str);
int N, S;
int fr[SMAX];

string Complete (string a, int N, char ch) {
    string ans = a;
    for (int i = 1; i <= N-a.size(); ++ i )
        ans.push_back(ch);
    return ans;
}

string Merge (string a, string b) {
    int poz_a = 0, poz_b = 0;
    int need = b.size();
    string pref;
    pref.clear();

    while (poz_a < a.size() && poz_b < b.size()) {
        string aux = pref + a[poz_a];
        for (int i = poz_b; i < b.size(); ++ i )
            aux.push_back(b[i]);
        int val = query(aux);
        if (val == aux.size()) {
            pref.push_back(a[poz_a]);
            ++ poz_a;
        }
        else {
            pref.push_back(b[poz_b]);
            ++ poz_b;
        }
    }

    for (int i = poz_a; i < a.size(); ++ i )
        pref.push_back(a[i]);
    for (int i = poz_b; i < b.size(); ++ i )
        pref.push_back(b[i]);

    return pref;
}

int Frequency (char ch) {
    string a = Complete("", N, ch);

    return query(a);
}

string guess (int n, int s) {
    N = n, S = s;
    string ans;
    for (int i = 1; i <= S; ++ i ) {
        char ch = 'a' + i - 1;
        fr[i] = Frequency(ch);
    }

    set <PIS> H;

    for (int i = 1; i <= S; ++ i ) {
        if (fr[i] == 0) continue;

        string aux;
        aux = Complete(aux, fr[i], i + 'a' - 1);
        H.insert({fr[i], aux});
    }

    while (H.size() >= 2) {
        set <PIS> :: iterator it = H.begin();
        PIS first = *it;
        it = next(it);
        PIS second = *it;
        H.erase(first);
        H.erase(second);

        H.insert({first.first + second.first, Merge(first.second, second.second)});
    }

    set <PIS> :: iterator it = H.begin();
    PIS yes = *it;

    ans = yes.second;

    return ans;
}

Compilation message (stderr)

password.cpp: In function 'std::string Complete(std::string, int, char)':
password.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i = 1; i <= N-a.size(); ++ i )
      |                     ~~^~~~~~~~~~~~~
password.cpp: In function 'std::string Merge(std::string, std::string)':
password.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while (poz_a < a.size() && poz_b < b.size()) {
      |            ~~~~~~^~~~~~~~~~
password.cpp:26:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while (poz_a < a.size() && poz_b < b.size()) {
      |                                ~~~~~~^~~~~~~~~~
password.cpp:28:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i = poz_b; i < b.size(); ++ i )
      |                             ~~^~~~~~~~~~
password.cpp:31:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         if (val == aux.size()) {
      |             ~~~~^~~~~~~~~~~~~
password.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = poz_a; i < a.size(); ++ i )
      |                         ~~^~~~~~~~~~
password.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = poz_b; i < b.size(); ++ i )
      |                         ~~^~~~~~~~~~
password.cpp:22:9: warning: unused variable 'need' [-Wunused-variable]
   22 |     int need = b.size();
      |         ^~~~

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