Submission #642610

#	Time	Username	Problem	Language	Result	Execution time	Memory
642610		MadokaMagicaFan	Password (RMI18_password)	C++14	100 / 100	328 ms	724 KiB

password

#include "bits/stdc++.h"

/* #define ONPC */
#define sz(v)       ((int)(v.size()))
#define pb          push_back

using namespace std;
int query(string);

string
gl(int n, int t)
{
    return string(n, 'a'+t);
}

int ask(string s, int n, int c) {
    return query(s + gl(n-sz(s), c));
}

string
guess(int n, int s)
{
    string pref;

    int rem[s];
    char calc[s];

    for (int i = 0; i < s; ++i) {
        rem[i] = query(gl(n,i));
        calc[i] = 0;
    }


    deque<int> ier;
    for (int i = 0; i < n; ++i) {
        int win = -1;
        int l, r, m;
        for (int j = 0; j < s; ++j) {
            if (rem[j] == 0) continue;
            if (calc[j]) continue;

            if (sz(ier) == 0) {
                ier.pb(j);
            } else {
                l = 0;
                r = sz(ier);

                while (l < r) {
                    m = (l+r) >> 1;
                    if (ask(pref + gl(1,j), n, ier[m]) > rem[ier[m]] + sz(pref))
                        r = m;
                    else
                        l = m + 1;
                }

                ier.pb(j);
                for (int z = sz(ier)-1; z > l; --z) {
                    ier[z] = ier[z-1];
                }
                ier[l] = j;
            }
            /* if (rem[j]) { */
            /*     if (win == -1) */
            /*         win = j; */
            /*     else { */
            /*         if (ask(pref+gl(1,j)+gl(rem[win], win), n) > rem[win] + sz(pref)) */
            /*             win = j; */
            /*     } */
            /* } */
            calc[j] = 1;
        }

        rem[ier[0]]--;
        calc[ier[0]] = 0;
        pref = pref + gl(1,ier[0]);

        ier.pop_front();
    }

    return pref;
}

#ifdef ONPC
int query(string s) {
    cout << s << endl;
    int x;
    cin >> x;
    return x;
}


int
main()
{
    int n, s;
    cin >> n >>s;
    cout << guess(n,s);

    return 0;
}
#endif

Compilation message (stderr)

password.cpp: In function 'std::string guess(int, int)':
password.cpp:36:13: warning: unused variable 'win' [-Wunused-variable]
   36 |         int win = -1;
      |             ^~~

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