oj.uz

Submission #1119135

# Submission time Handle Problem Language Result Execution time Memory
1119135 2024-11-26T16:15:51 Z somefolk Password (RMI18_password) C++17
100 / 100
 984 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 80 queries.
2 Correct 3 ms 336 KB Guessed the password with 143 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 48 queries.
2 Correct 4 ms 336 KB Guessed the password with 105 queries.
3 Correct 3 ms 592 KB Guessed the password with 97 queries.
4 Correct 6 ms 592 KB Guessed the password with 205 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 716 KB Guessed the password with 3787 queries.
2 Correct 112 ms 724 KB Guessed the password with 5019 queries.
3 Correct 178 ms 960 KB Guessed the password with 7587 queries.
4 Correct 261 ms 720 KB Guessed the password with 11878 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 80 queries.
2 Correct 3 ms 336 KB Guessed the password with 143 queries.
3 Correct 2 ms 336 KB Guessed the password with 48 queries.
4 Correct 4 ms 336 KB Guessed the password with 105 queries.
5 Correct 3 ms 592 KB Guessed the password with 97 queries.
6 Correct 6 ms 592 KB Guessed the password with 205 queries.
7 Correct 81 ms 716 KB Guessed the password with 3787 queries.
8 Correct 112 ms 724 KB Guessed the password with 5019 queries.
9 Correct 178 ms 960 KB Guessed the password with 7587 queries.
10 Correct 261 ms 720 KB Guessed the password with 11878 queries.
11 Correct 322 ms 712 KB Guessed the password with 13923 queries.
12 Correct 328 ms 748 KB Guessed the password with 13734 queries.
13 Correct 422 ms 488 KB Guessed the password with 18461 queries.
14 Correct 418 ms 492 KB Guessed the password with 19072 queries.
15 Correct 394 ms 964 KB Guessed the password with 17596 queries.
16 Correct 428 ms 748 KB Guessed the password with 18716 queries.
17 Correct 369 ms 704 KB Guessed the password with 16224 queries.
18 Correct 354 ms 1216 KB Guessed the password with 15508 queries.
19 Correct 364 ms 960 KB Guessed the password with 15400 queries.
20 Correct 375 ms 524 KB Guessed the password with 15493 queries.
21 Correct 291 ms 960 KB Guessed the password with 12116 queries.
22 Correct 278 ms 720 KB Guessed the password with 11630 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 80 queries.
2 Correct 3 ms 336 KB Guessed the password with 143 queries.
3 Correct 2 ms 336 KB Guessed the password with 48 queries.
4 Correct 4 ms 336 KB Guessed the password with 105 queries.
5 Correct 3 ms 592 KB Guessed the password with 97 queries.
6 Correct 6 ms 592 KB Guessed the password with 205 queries.
7 Correct 81 ms 716 KB Guessed the password with 3787 queries.
8 Correct 112 ms 724 KB Guessed the password with 5019 queries.
9 Correct 178 ms 960 KB Guessed the password with 7587 queries.
10 Correct 261 ms 720 KB Guessed the password with 11878 queries.
11 Correct 322 ms 712 KB Guessed the password with 13923 queries.
12 Correct 328 ms 748 KB Guessed the password with 13734 queries.
13 Correct 422 ms 488 KB Guessed the password with 18461 queries.
14 Correct 418 ms 492 KB Guessed the password with 19072 queries.
15 Correct 394 ms 964 KB Guessed the password with 17596 queries.
16 Correct 428 ms 748 KB Guessed the password with 18716 queries.
17 Correct 369 ms 704 KB Guessed the password with 16224 queries.
18 Correct 354 ms 1216 KB Guessed the password with 15508 queries.
19 Correct 364 ms 960 KB Guessed the password with 15400 queries.
20 Correct 375 ms 524 KB Guessed the password with 15493 queries.
21 Correct 291 ms 960 KB Guessed the password with 12116 queries.
22 Correct 278 ms 720 KB Guessed the password with 11630 queries.
23 Correct 589 ms 1372 KB Guessed the password with 25356 queries.
24 Correct 508 ms 1368 KB Guessed the password with 21699 queries.
25 Correct 807 ms 1364 KB Guessed the password with 37521 queries.
26 Correct 641 ms 1416 KB Guessed the password with 30198 queries.
27 Correct 869 ms 1820 KB Guessed the password with 41137 queries.
28 Correct 670 ms 1924 KB Guessed the password with 28031 queries.
29 Correct 984 ms 1792 KB Guessed the password with 42856 queries.
30 Correct 564 ms 1764 KB Guessed the password with 23750 queries.