oj.uz

답안 #709219

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709219 2023-03-13T08:40:41 Z maomao90 Password (RMI18_password) C++17
50 / 100
 429 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Guessed the password with 121 queries.
2 Correct 3 ms 336 KB Guessed the password with 277 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 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 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

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 336 KB Guessed the password with 9609 queries.
2 Correct 112 ms 336 KB Guessed the password with 17345 queries.
3 Correct 170 ms 464 KB Guessed the password with 21757 queries.
4 Correct 349 ms 464 KB Guessed the password with 36499 queries.

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Guessed the password with 121 queries.
2 Correct 3 ms 336 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 2 ms 208 KB Guessed the password with 170 queries.
6 Correct 3 ms 208 KB Guessed the password with 293 queries.
7 Correct 92 ms 336 KB Guessed the password with 9609 queries.
8 Correct 112 ms 336 KB Guessed the password with 17345 queries.
9 Correct 170 ms 464 KB Guessed the password with 21757 queries.
10 Correct 349 ms 464 KB Guessed the password with 36499 queries.
11 Incorrect 429 ms 592 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Guessed the password with 121 queries.
2 Correct 3 ms 336 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 2 ms 208 KB Guessed the password with 170 queries.
6 Correct 3 ms 208 KB Guessed the password with 293 queries.
7 Correct 92 ms 336 KB Guessed the password with 9609 queries.
8 Correct 112 ms 336 KB Guessed the password with 17345 queries.
9 Correct 170 ms 464 KB Guessed the password with 21757 queries.
10 Correct 349 ms 464 KB Guessed the password with 36499 queries.
11 Incorrect 429 ms 592 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -