oj.uz

Submission #642650

# Submission time Handle Problem Language Result Execution time Memory
642650 2022-09-20T10:06:17 Z SlavicG Password (RMI18_password) C++17
50 / 100
 869 ms 484 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());
    reverse(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;
    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 156 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 52 queries.
2 Correct 2 ms 208 KB Guessed the password with 128 queries.
3 Correct 2 ms 300 KB Guessed the password with 181 queries.
4 Correct 2 ms 208 KB Guessed the password with 264 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 344 KB Guessed the password with 8257 queries.
2 Correct 124 ms 352 KB Guessed the password with 10639 queries.
3 Correct 275 ms 336 KB Guessed the password with 19403 queries.
4 Correct 420 ms 356 KB Guessed the password with 26461 queries.

Subtask #4
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 156 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 2 ms 208 KB Guessed the password with 128 queries.
5 Correct 2 ms 300 KB Guessed the password with 181 queries.
6 Correct 2 ms 208 KB Guessed the password with 264 queries.
7 Correct 107 ms 344 KB Guessed the password with 8257 queries.
8 Correct 124 ms 352 KB Guessed the password with 10639 queries.
9 Correct 275 ms 336 KB Guessed the password with 19403 queries.
10 Correct 420 ms 356 KB Guessed the password with 26461 queries.
11 Incorrect 869 ms 484 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 87 queries.
2 Correct 2 ms 208 KB Guessed the password with 156 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 2 ms 208 KB Guessed the password with 128 queries.
5 Correct 2 ms 300 KB Guessed the password with 181 queries.
6 Correct 2 ms 208 KB Guessed the password with 264 queries.
7 Correct 107 ms 344 KB Guessed the password with 8257 queries.
8 Correct 124 ms 352 KB Guessed the password with 10639 queries.
9 Correct 275 ms 336 KB Guessed the password with 19403 queries.
10 Correct 420 ms 356 KB Guessed the password with 26461 queries.
11 Incorrect 869 ms 484 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -