oj.uz

답안 #1119133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1119133 2024-11-26T16:14:39 Z somefolk Password (RMI18_password) C++14
100 / 100
 975 ms 1924 KB 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <complex>
#include <list>
#include <chrono>
#include <random>
#include <stack>
#include <iomanip>
#include <fstream>
#include <cassert>
using namespace std;

#define endl "\n"
// #define int long long

const int INF = 2 * 1e5 + 5;
const int MOD = 1e9 + 7;

// int query(string s){
//     int n;
//     cout << s;
//     cin >> n;
//     return n;
// }

int query(string s);

string guess(int n, int s){
    vector<char> a;
    unordered_map<char, int> mp;
    unordered_map<char, char> adj;
    for(char i = 'a'; i < 'a'+s; i++){
        int amount = query(string(n, i));
        if(amount != 0){
            a.push_back(i);
            mp[i] = amount;
        }
    }

    string sol = "";
    for(int i = 0; i < n; i++){
        // randomize:
        random_device rd;
        mt19937 g(rd());
        shuffle(a.begin(), a.end(), g);

        // get edeges between letters:
        if(i == 0 || a.size() > 1){
            char prev = a[0];
            for(auto &j : a){
                if(prev == j) continue;
                if(query(sol + j + string(mp[prev], prev)) == (int)sol.size() +  mp[prev] + 1){
                    adj[prev] = j;
                    prev = j;
                } else {
                    adj[j] = prev;
                }
            }
        }

        // dfs for last
        char end = a[0];
        while(true){
            if(adj.count(end) == 0) break;
            end = adj[end];
        }

        sol+=end;
        mp[end]--;

        // erase last and all edges to last
        vector<char> dis;
        if(mp[end]) dis.push_back(end);
        for(auto it = adj.begin(); it != adj.end();){
            if(it->second == end){
                dis.push_back(it->first);
                it = adj.erase(it);
            } else {
                it++;
            }
        }

        a.clear();
        a = dis;
    }

    return sol;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 336 KB Guessed the password with 49 queries.
2 Correct 3 ms 336 KB Guessed the password with 96 queries.
3 Correct 3 ms 448 KB Guessed the password with 94 queries.
4 Correct 5 ms 444 KB Guessed the password with 213 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 456 KB Guessed the password with 3892 queries.
2 Correct 113 ms 712 KB Guessed the password with 5073 queries.
3 Correct 162 ms 712 KB Guessed the password with 7670 queries.
4 Correct 260 ms 712 KB Guessed the password with 12098 queries.

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 336 KB Guessed the password with 83 queries.
2 Correct 4 ms 336 KB Guessed the password with 145 queries.
3 Correct 2 ms 336 KB Guessed the password with 49 queries.
4 Correct 3 ms 336 KB Guessed the password with 96 queries.
5 Correct 3 ms 448 KB Guessed the password with 94 queries.
6 Correct 5 ms 444 KB Guessed the password with 213 queries.
7 Correct 85 ms 456 KB Guessed the password with 3892 queries.
8 Correct 113 ms 712 KB Guessed the password with 5073 queries.
9 Correct 162 ms 712 KB Guessed the password with 7670 queries.
10 Correct 260 ms 712 KB Guessed the password with 12098 queries.
11 Correct 297 ms 712 KB Guessed the password with 13397 queries.
12 Correct 321 ms 720 KB Guessed the password with 13481 queries.
13 Correct 410 ms 740 KB Guessed the password with 18834 queries.
14 Correct 374 ms 720 KB Guessed the password with 18402 queries.
15 Correct 393 ms 740 KB Guessed the password with 18127 queries.
16 Correct 399 ms 972 KB Guessed the password with 19016 queries.
17 Correct 361 ms 704 KB Guessed the password with 15757 queries.
18 Correct 354 ms 496 KB Guessed the password with 15665 queries.
19 Correct 366 ms 976 KB Guessed the password with 15793 queries.
20 Correct 367 ms 724 KB Guessed the password with 15439 queries.
21 Correct 308 ms 1220 KB Guessed the password with 12086 queries.
22 Correct 273 ms 744 KB Guessed the password with 11443 queries.

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 336 KB Guessed the password with 83 queries.
2 Correct 4 ms 336 KB Guessed the password with 145 queries.
3 Correct 2 ms 336 KB Guessed the password with 49 queries.
4 Correct 3 ms 336 KB Guessed the password with 96 queries.
5 Correct 3 ms 448 KB Guessed the password with 94 queries.
6 Correct 5 ms 444 KB Guessed the password with 213 queries.
7 Correct 85 ms 456 KB Guessed the password with 3892 queries.
8 Correct 113 ms 712 KB Guessed the password with 5073 queries.
9 Correct 162 ms 712 KB Guessed the password with 7670 queries.
10 Correct 260 ms 712 KB Guessed the password with 12098 queries.
11 Correct 297 ms 712 KB Guessed the password with 13397 queries.
12 Correct 321 ms 720 KB Guessed the password with 13481 queries.
13 Correct 410 ms 740 KB Guessed the password with 18834 queries.
14 Correct 374 ms 720 KB Guessed the password with 18402 queries.
15 Correct 393 ms 740 KB Guessed the password with 18127 queries.
16 Correct 399 ms 972 KB Guessed the password with 19016 queries.
17 Correct 361 ms 704 KB Guessed the password with 15757 queries.
18 Correct 354 ms 496 KB Guessed the password with 15665 queries.
19 Correct 366 ms 976 KB Guessed the password with 15793 queries.
20 Correct 367 ms 724 KB Guessed the password with 15439 queries.
21 Correct 308 ms 1220 KB Guessed the password with 12086 queries.
22 Correct 273 ms 744 KB Guessed the password with 11443 queries.
23 Correct 568 ms 1352 KB Guessed the password with 24967 queries.
24 Correct 507 ms 964 KB Guessed the password with 21369 queries.
25 Correct 798 ms 1924 KB Guessed the password with 37694 queries.
26 Correct 692 ms 1544 KB Guessed the password with 30776 queries.
27 Correct 919 ms 1608 KB Guessed the password with 40664 queries.
28 Correct 632 ms 1884 KB Guessed the password with 27529 queries.
29 Correct 975 ms 1556 KB Guessed the password with 42846 queries.
30 Correct 607 ms 1640 KB Guessed the password with 23905 queries.