oj.uz

Submission #709220

# Submission time Handle Problem Language Result Execution time Memory
709220 2023-03-13T08:41:02 Z maomao90 Password (RMI18_password) C++17
50 / 100
 459 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);
    }
    vi id(s, 0);
    iota(ALL(id), 0);
    sort(ALL(id), [&] (int l, int r) {
            return occ[l] < occ[r];
            });
    REP (i, 0, s) {
        REP (j, 0, n) {
            pos[i][j] = 0;
        }
    }
    /*
    REP (li, 0, s) {
        int l = id[li];
        REP (ri, li + 1, s) {
            int r = id[ri];
            string str(n, 'a' + r);
            cerr << str << '\n';
            REP (i, 0, occ[l]) {
                str[n - i - 1] = 'a' + l;
            }
            int px = 0;
            RREP (i, occ[l], 1) {
                int x = query(str) - i;
                cerr << str << ' ' << x << '\n';
                pos[l][occ[l] - i] += x;
                REP (j, px, x) {
                    pos[r][j] += occ[l] - i;
                }
                px = x;
                str[n - i] = 'a' + r;
            }
        }
    }
    */
    REP (li, 0, s) {
        int l = id[li];
        REP (ri, li + 1, s) {
            int r = id[ri];
            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 308 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 2 ms 208 KB Guessed the password with 133 queries.
3 Correct 3 ms 208 KB Guessed the password with 170 queries.
4 Correct 2 ms 308 KB Guessed the password with 293 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 336 KB Guessed the password with 9609 queries.
2 Correct 108 ms 436 KB Guessed the password with 17345 queries.
3 Correct 213 ms 464 KB Guessed the password with 21757 queries.
4 Correct 367 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 308 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 2 ms 208 KB Guessed the password with 133 queries.
5 Correct 3 ms 208 KB Guessed the password with 170 queries.
6 Correct 2 ms 308 KB Guessed the password with 293 queries.
7 Correct 105 ms 336 KB Guessed the password with 9609 queries.
8 Correct 108 ms 436 KB Guessed the password with 17345 queries.
9 Correct 213 ms 464 KB Guessed the password with 21757 queries.
10 Correct 367 ms 464 KB Guessed the password with 36499 queries.
11 Incorrect 459 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 308 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 2 ms 208 KB Guessed the password with 133 queries.
5 Correct 3 ms 208 KB Guessed the password with 170 queries.
6 Correct 2 ms 308 KB Guessed the password with 293 queries.
7 Correct 105 ms 336 KB Guessed the password with 9609 queries.
8 Correct 108 ms 436 KB Guessed the password with 17345 queries.
9 Correct 213 ms 464 KB Guessed the password with 21757 queries.
10 Correct 367 ms 464 KB Guessed the password with 36499 queries.
11 Incorrect 459 ms 592 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -