oj.uz

Submission #709194

# Submission time Handle Problem Language Result Execution time Memory
709194 2023-03-13T07:48:35 Z maomao90 Password (RMI18_password) C++17
50 / 100
 384 ms 592 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 5005;

int query(string str);

int occ[30];
int pos[30][MAXN];
string guess(int n, int s) {
    REP (c, 0, s) {
        string str(n, 'a' + c);
        occ[c] = query(str);
    }
    REP (i, 0, s) {
        REP (j, 0, n) {
            pos[i][j] = 0;
        }
    }
    REP (l, 0, s) {
        REP (r, l + 1, s) {
            int ptr = occ[r];
            auto make = [&] (int x, int y) {
                string s = "";
                REP (i, 0, x) {
                    s += l + 'a';
                }
                REP (i, 0, y) {
                    s += r + 'a';
                }
                return s;
            };
            REP (i, 1, occ[l] + 1) {
                while (ptr >= 1 && query(make(i, ptr)) != i + ptr) {
                    pos[r][occ[r] - ptr] += i - 1;
                    ptr--;
                }
                pos[l][i - 1] += occ[r] - ptr;
            }
            while (ptr >= 1) {
                pos[r][occ[r] - ptr] += occ[l];
                ptr--;
            }
        }
    }
    string ans(n, '?');
    REP (c, 0, s) {
        REP (i, 0, occ[c]) {
            ans[pos[c][i] + i] = 'a' + c;
        }
    }
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Guessed the password with 121 queries.
2 Correct 2 ms 336 KB Guessed the password with 277 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 312 KB Guessed the password with 133 queries.
3 Correct 3 ms 208 KB Guessed the password with 170 queries.
4 Correct 4 ms 208 KB Guessed the password with 293 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 304 KB Guessed the password with 9609 queries.
2 Correct 126 ms 444 KB Guessed the password with 17345 queries.
3 Correct 218 ms 464 KB Guessed the password with 21757 queries.
4 Correct 372 ms 464 KB Guessed the password with 36499 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Guessed the password with 121 queries.
2 Correct 2 ms 336 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 1 ms 312 KB Guessed the password with 133 queries.
5 Correct 3 ms 208 KB Guessed the password with 170 queries.
6 Correct 4 ms 208 KB Guessed the password with 293 queries.
7 Correct 101 ms 304 KB Guessed the password with 9609 queries.
8 Correct 126 ms 444 KB Guessed the password with 17345 queries.
9 Correct 218 ms 464 KB Guessed the password with 21757 queries.
10 Correct 372 ms 464 KB Guessed the password with 36499 queries.
11 Incorrect 384 ms 592 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 336 KB Guessed the password with 121 queries.
2 Correct 2 ms 336 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 1 ms 312 KB Guessed the password with 133 queries.
5 Correct 3 ms 208 KB Guessed the password with 170 queries.
6 Correct 4 ms 208 KB Guessed the password with 293 queries.
7 Correct 101 ms 304 KB Guessed the password with 9609 queries.
8 Correct 126 ms 444 KB Guessed the password with 17345 queries.
9 Correct 218 ms 464 KB Guessed the password with 21757 queries.
10 Correct 372 ms 464 KB Guessed the password with 36499 queries.
11 Incorrect 384 ms 592 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -