oj.uz

Submission #642648

# Submission time Handle Problem Language Result Execution time Memory
642648 2022-09-20T10:04:42 Z SlavicG Password (RMI18_password) C++17
80 / 100
 808 ms 604 KB 
#include "bits/stdc++.h"
using namespace std;
int query(string str);

#define sz(a) (int)a.size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string guess(int n, int s) {
    vector<pair<int, char>> v;
    for(int f = 0; f < s; ++f) {
        char c = char('a' + f);
        string paiu = string(n, c);
        int x = query(paiu);
        if(x > 0) {
            v.push_back({x, c});
        }
    }
    assert(v.size() > 0);
    sort(v.begin(), v.end());
    string ans = string(v[0].first, v[0].second);
    v.erase(v.begin());

    assert(sz(ans) > 0);
    if(!sz(v)) return ans;
    shuffle(v.begin(), v.end(), rng);
    for(auto noo: v) {
        char c = noo.second;
        int cnt = noo.first;
        vector<int> add(sz(ans) + 5, 0);
        string ff = ans;
        string bruh = "";
        for(int i = 0; i <= sz(ff); ++i) {
            int lol = 0;
            for(int j = 0; j < cnt; ++j) {
                bruh += c;
                string paiu = bruh;
                for(int k = i; k < sz(ff); ++k) paiu += ff[k];
                if(query(paiu) == sz(paiu)) {
                    ++lol;
                } else {
                    bruh.pop_back();
                    break;
                }
            }
            cnt -= lol;
            if(i < sz(ff)) bruh += ff[i];
        }
        ans = bruh;
    }
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 87 queries.
2 Correct 2 ms 208 KB Guessed the password with 194 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 119 queries.
3 Correct 1 ms 208 KB Guessed the password with 91 queries.
4 Correct 2 ms 208 KB Guessed the password with 221 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 336 KB Guessed the password with 5653 queries.
2 Correct 121 ms 352 KB Guessed the password with 9565 queries.
3 Correct 127 ms 460 KB Guessed the password with 9764 queries.
4 Correct 276 ms 488 KB Guessed the password with 21309 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 87 queries.
2 Correct 2 ms 208 KB Guessed the password with 194 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 119 queries.
5 Correct 1 ms 208 KB Guessed the password with 91 queries.
6 Correct 2 ms 208 KB Guessed the password with 221 queries.
7 Correct 68 ms 336 KB Guessed the password with 5653 queries.
8 Correct 121 ms 352 KB Guessed the password with 9565 queries.
9 Correct 127 ms 460 KB Guessed the password with 9764 queries.
10 Correct 276 ms 488 KB Guessed the password with 21309 queries.
11 Correct 533 ms 456 KB Guessed the password with 34650 queries.
12 Correct 343 ms 484 KB Guessed the password with 23412 queries.
13 Correct 411 ms 364 KB Guessed the password with 33513 queries.
14 Correct 597 ms 480 KB Guessed the password with 37532 queries.
15 Correct 365 ms 476 KB Guessed the password with 25822 queries.
16 Correct 405 ms 496 KB Guessed the password with 24859 queries.
17 Correct 467 ms 492 KB Guessed the password with 28490 queries.
18 Correct 523 ms 376 KB Guessed the password with 28123 queries.
19 Correct 737 ms 372 KB Guessed the password with 37450 queries.
20 Correct 332 ms 428 KB Guessed the password with 23169 queries.
21 Correct 787 ms 596 KB Guessed the password with 43488 queries.
22 Correct 255 ms 460 KB Guessed the password with 22477 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 87 queries.
2 Correct 2 ms 208 KB Guessed the password with 194 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 119 queries.
5 Correct 1 ms 208 KB Guessed the password with 91 queries.
6 Correct 2 ms 208 KB Guessed the password with 221 queries.
7 Correct 68 ms 336 KB Guessed the password with 5653 queries.
8 Correct 121 ms 352 KB Guessed the password with 9565 queries.
9 Correct 127 ms 460 KB Guessed the password with 9764 queries.
10 Correct 276 ms 488 KB Guessed the password with 21309 queries.
11 Correct 533 ms 456 KB Guessed the password with 34650 queries.
12 Correct 343 ms 484 KB Guessed the password with 23412 queries.
13 Correct 411 ms 364 KB Guessed the password with 33513 queries.
14 Correct 597 ms 480 KB Guessed the password with 37532 queries.
15 Correct 365 ms 476 KB Guessed the password with 25822 queries.
16 Correct 405 ms 496 KB Guessed the password with 24859 queries.
17 Correct 467 ms 492 KB Guessed the password with 28490 queries.
18 Correct 523 ms 376 KB Guessed the password with 28123 queries.
19 Correct 737 ms 372 KB Guessed the password with 37450 queries.
20 Correct 332 ms 428 KB Guessed the password with 23169 queries.
21 Correct 787 ms 596 KB Guessed the password with 43488 queries.
22 Correct 255 ms 460 KB Guessed the password with 22477 queries.
23 Incorrect 808 ms 604 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -