oj.uz

Submission #1119126

# Submission time Handle Problem Language Result Execution time Memory
1119126 2024-11-26T16:13:04 Z somefolk Password (RMI18_password) C++14
100 / 100
 929 ms 1824 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 66 queries.
2 Correct 4 ms 336 KB Guessed the password with 125 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Guessed the password with 48 queries.
2 Correct 4 ms 336 KB Guessed the password with 107 queries.
3 Correct 4 ms 500 KB Guessed the password with 93 queries.
4 Correct 6 ms 336 KB Guessed the password with 213 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 716 KB Guessed the password with 3966 queries.
2 Correct 103 ms 700 KB Guessed the password with 4973 queries.
3 Correct 172 ms 476 KB Guessed the password with 7566 queries.
4 Correct 275 ms 724 KB Guessed the password with 12125 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 66 queries.
2 Correct 4 ms 336 KB Guessed the password with 125 queries.
3 Correct 3 ms 336 KB Guessed the password with 48 queries.
4 Correct 4 ms 336 KB Guessed the password with 107 queries.
5 Correct 4 ms 500 KB Guessed the password with 93 queries.
6 Correct 6 ms 336 KB Guessed the password with 213 queries.
7 Correct 88 ms 716 KB Guessed the password with 3966 queries.
8 Correct 103 ms 700 KB Guessed the password with 4973 queries.
9 Correct 172 ms 476 KB Guessed the password with 7566 queries.
10 Correct 275 ms 724 KB Guessed the password with 12125 queries.
11 Correct 303 ms 740 KB Guessed the password with 13603 queries.
12 Correct 291 ms 724 KB Guessed the password with 13468 queries.
13 Correct 380 ms 968 KB Guessed the password with 18189 queries.
14 Correct 418 ms 716 KB Guessed the password with 18512 queries.
15 Correct 373 ms 744 KB Guessed the password with 18263 queries.
16 Correct 417 ms 496 KB Guessed the password with 17865 queries.
17 Correct 372 ms 716 KB Guessed the password with 15655 queries.
18 Correct 362 ms 492 KB Guessed the password with 16234 queries.
19 Correct 345 ms 960 KB Guessed the password with 15552 queries.
20 Correct 378 ms 724 KB Guessed the password with 15540 queries.
21 Correct 278 ms 488 KB Guessed the password with 12331 queries.
22 Correct 272 ms 712 KB Guessed the password with 11480 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 66 queries.
2 Correct 4 ms 336 KB Guessed the password with 125 queries.
3 Correct 3 ms 336 KB Guessed the password with 48 queries.
4 Correct 4 ms 336 KB Guessed the password with 107 queries.
5 Correct 4 ms 500 KB Guessed the password with 93 queries.
6 Correct 6 ms 336 KB Guessed the password with 213 queries.
7 Correct 88 ms 716 KB Guessed the password with 3966 queries.
8 Correct 103 ms 700 KB Guessed the password with 4973 queries.
9 Correct 172 ms 476 KB Guessed the password with 7566 queries.
10 Correct 275 ms 724 KB Guessed the password with 12125 queries.
11 Correct 303 ms 740 KB Guessed the password with 13603 queries.
12 Correct 291 ms 724 KB Guessed the password with 13468 queries.
13 Correct 380 ms 968 KB Guessed the password with 18189 queries.
14 Correct 418 ms 716 KB Guessed the password with 18512 queries.
15 Correct 373 ms 744 KB Guessed the password with 18263 queries.
16 Correct 417 ms 496 KB Guessed the password with 17865 queries.
17 Correct 372 ms 716 KB Guessed the password with 15655 queries.
18 Correct 362 ms 492 KB Guessed the password with 16234 queries.
19 Correct 345 ms 960 KB Guessed the password with 15552 queries.
20 Correct 378 ms 724 KB Guessed the password with 15540 queries.
21 Correct 278 ms 488 KB Guessed the password with 12331 queries.
22 Correct 272 ms 712 KB Guessed the password with 11480 queries.
23 Correct 576 ms 1372 KB Guessed the password with 25495 queries.
24 Correct 511 ms 944 KB Guessed the password with 21296 queries.
25 Correct 858 ms 1824 KB Guessed the password with 37832 queries.
26 Correct 621 ms 1568 KB Guessed the password with 30403 queries.
27 Correct 786 ms 1700 KB Guessed the password with 40776 queries.
28 Correct 643 ms 1040 KB Guessed the password with 27865 queries.
29 Correct 929 ms 1768 KB Guessed the password with 42447 queries.
30 Correct 616 ms 1556 KB Guessed the password with 24055 queries.