oj.uz

Submission #642606

# Submission time Handle Problem Language Result Execution time Memory
642606 2022-09-20T08:36:29 Z MadokaMagicaFan Password (RMI18_password) C++14
50 / 100
 380 ms 700 KB 
#include "bits/stdc++.h"

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

using namespace std;
int query(string);

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

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

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

    int rem[s];

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

    for (int i = 0; i < n; ++i) {
        int win = -1;
        for (int j = 0; j < s; ++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;
                }
            }
        }

        rem[win]--;

        pref = pref + gl(1,win);
    }

    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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 120 queries.
2 Correct 4 ms 208 KB Guessed the password with 276 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 48 queries.
2 Correct 2 ms 208 KB Guessed the password with 132 queries.
3 Correct 2 ms 208 KB Guessed the password with 170 queries.
4 Correct 3 ms 208 KB Guessed the password with 293 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 436 KB Guessed the password with 9608 queries.
2 Correct 104 ms 436 KB Guessed the password with 17344 queries.
3 Correct 119 ms 420 KB Guessed the password with 21757 queries.
4 Correct 233 ms 392 KB Guessed the password with 36499 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 120 queries.
2 Correct 4 ms 208 KB Guessed the password with 276 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 132 queries.
5 Correct 2 ms 208 KB Guessed the password with 170 queries.
6 Correct 3 ms 208 KB Guessed the password with 293 queries.
7 Correct 73 ms 436 KB Guessed the password with 9608 queries.
8 Correct 104 ms 436 KB Guessed the password with 17344 queries.
9 Correct 119 ms 420 KB Guessed the password with 21757 queries.
10 Correct 233 ms 392 KB Guessed the password with 36499 queries.
11 Incorrect 380 ms 700 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 120 queries.
2 Correct 4 ms 208 KB Guessed the password with 276 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 132 queries.
5 Correct 2 ms 208 KB Guessed the password with 170 queries.
6 Correct 3 ms 208 KB Guessed the password with 293 queries.
7 Correct 73 ms 436 KB Guessed the password with 9608 queries.
8 Correct 104 ms 436 KB Guessed the password with 17344 queries.
9 Correct 119 ms 420 KB Guessed the password with 21757 queries.
10 Correct 233 ms 392 KB Guessed the password with 36499 queries.
11 Incorrect 380 ms 700 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -