oj.uz

Submission #642610

# Submission time Handle Problem Language Result Execution time Memory
642610 2022-09-20T08:50:56 Z MadokaMagicaFan Password (RMI18_password) C++14
100 / 100
 328 ms 724 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 56 queries.
2 Correct 1 ms 208 KB Guessed the password with 101 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 49 queries.
2 Correct 1 ms 208 KB Guessed the password with 124 queries.
3 Correct 2 ms 208 KB Guessed the password with 169 queries.
4 Correct 2 ms 208 KB Guessed the password with 200 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 304 KB Guessed the password with 3622 queries.
2 Correct 56 ms 308 KB Guessed the password with 5102 queries.
3 Correct 75 ms 420 KB Guessed the password with 6294 queries.
4 Correct 109 ms 352 KB Guessed the password with 8985 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 56 queries.
2 Correct 1 ms 208 KB Guessed the password with 101 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 1 ms 208 KB Guessed the password with 124 queries.
5 Correct 2 ms 208 KB Guessed the password with 169 queries.
6 Correct 2 ms 208 KB Guessed the password with 200 queries.
7 Correct 32 ms 304 KB Guessed the password with 3622 queries.
8 Correct 56 ms 308 KB Guessed the password with 5102 queries.
9 Correct 75 ms 420 KB Guessed the password with 6294 queries.
10 Correct 109 ms 352 KB Guessed the password with 8985 queries.
11 Correct 98 ms 432 KB Guessed the password with 12792 queries.
12 Correct 142 ms 452 KB Guessed the password with 11932 queries.
13 Correct 142 ms 456 KB Guessed the password with 14072 queries.
14 Correct 121 ms 428 KB Guessed the password with 14202 queries.
15 Correct 124 ms 568 KB Guessed the password with 14355 queries.
16 Correct 114 ms 372 KB Guessed the password with 14135 queries.
17 Correct 123 ms 420 KB Guessed the password with 14271 queries.
18 Correct 104 ms 404 KB Guessed the password with 15067 queries.
19 Correct 157 ms 468 KB Guessed the password with 14768 queries.
20 Correct 138 ms 428 KB Guessed the password with 13704 queries.
21 Correct 159 ms 288 KB Guessed the password with 16229 queries.
22 Correct 105 ms 432 KB Guessed the password with 15121 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 56 queries.
2 Correct 1 ms 208 KB Guessed the password with 101 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 1 ms 208 KB Guessed the password with 124 queries.
5 Correct 2 ms 208 KB Guessed the password with 169 queries.
6 Correct 2 ms 208 KB Guessed the password with 200 queries.
7 Correct 32 ms 304 KB Guessed the password with 3622 queries.
8 Correct 56 ms 308 KB Guessed the password with 5102 queries.
9 Correct 75 ms 420 KB Guessed the password with 6294 queries.
10 Correct 109 ms 352 KB Guessed the password with 8985 queries.
11 Correct 98 ms 432 KB Guessed the password with 12792 queries.
12 Correct 142 ms 452 KB Guessed the password with 11932 queries.
13 Correct 142 ms 456 KB Guessed the password with 14072 queries.
14 Correct 121 ms 428 KB Guessed the password with 14202 queries.
15 Correct 124 ms 568 KB Guessed the password with 14355 queries.
16 Correct 114 ms 372 KB Guessed the password with 14135 queries.
17 Correct 123 ms 420 KB Guessed the password with 14271 queries.
18 Correct 104 ms 404 KB Guessed the password with 15067 queries.
19 Correct 157 ms 468 KB Guessed the password with 14768 queries.
20 Correct 138 ms 428 KB Guessed the password with 13704 queries.
21 Correct 159 ms 288 KB Guessed the password with 16229 queries.
22 Correct 105 ms 432 KB Guessed the password with 15121 queries.
23 Correct 265 ms 552 KB Guessed the password with 24500 queries.
24 Correct 314 ms 548 KB Guessed the password with 24132 queries.
25 Correct 248 ms 636 KB Guessed the password with 24120 queries.
26 Correct 328 ms 600 KB Guessed the password with 23734 queries.
27 Correct 252 ms 476 KB Guessed the password with 23920 queries.
28 Correct 285 ms 724 KB Guessed the password with 22684 queries.
29 Correct 213 ms 504 KB Guessed the password with 23825 queries.
30 Correct 203 ms 596 KB Guessed the password with 22052 queries.