oj.uz

Submission #1119130

# Submission time Handle Problem Language Result Execution time Memory
1119130 2024-11-26T16:14:11 Z somefolk Password (RMI18_password) C++17
50 / 100
 401 ms 1224 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 72 queries.
2 Correct 4 ms 444 KB Guessed the password with 137 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 3 ms 336 KB Guessed the password with 100 queries.
3 Correct 5 ms 592 KB Guessed the password with 92 queries.
4 Correct 7 ms 444 KB Guessed the password with 223 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 716 KB Guessed the password with 3515 queries.
2 Correct 114 ms 724 KB Guessed the password with 5085 queries.
3 Correct 169 ms 1224 KB Guessed the password with 7345 queries.
4 Correct 252 ms 724 KB Guessed the password with 12227 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 72 queries.
2 Correct 4 ms 444 KB Guessed the password with 137 queries.
3 Correct 3 ms 336 KB Guessed the password with 48 queries.
4 Correct 3 ms 336 KB Guessed the password with 100 queries.
5 Correct 5 ms 592 KB Guessed the password with 92 queries.
6 Correct 7 ms 444 KB Guessed the password with 223 queries.
7 Correct 83 ms 716 KB Guessed the password with 3515 queries.
8 Correct 114 ms 724 KB Guessed the password with 5085 queries.
9 Correct 169 ms 1224 KB Guessed the password with 7345 queries.
10 Correct 252 ms 724 KB Guessed the password with 12227 queries.
11 Correct 321 ms 740 KB Guessed the password with 13873 queries.
12 Correct 260 ms 968 KB Guessed the password with 13859 queries.
13 Correct 306 ms 720 KB Guessed the password with 18650 queries.
14 Correct 372 ms 700 KB Guessed the password with 19036 queries.
15 Correct 390 ms 716 KB Guessed the password with 18604 queries.
16 Correct 401 ms 720 KB Guessed the password with 18774 queries.
17 Runtime error 325 ms 744 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 72 queries.
2 Correct 4 ms 444 KB Guessed the password with 137 queries.
3 Correct 3 ms 336 KB Guessed the password with 48 queries.
4 Correct 3 ms 336 KB Guessed the password with 100 queries.
5 Correct 5 ms 592 KB Guessed the password with 92 queries.
6 Correct 7 ms 444 KB Guessed the password with 223 queries.
7 Correct 83 ms 716 KB Guessed the password with 3515 queries.
8 Correct 114 ms 724 KB Guessed the password with 5085 queries.
9 Correct 169 ms 1224 KB Guessed the password with 7345 queries.
10 Correct 252 ms 724 KB Guessed the password with 12227 queries.
11 Correct 321 ms 740 KB Guessed the password with 13873 queries.
12 Correct 260 ms 968 KB Guessed the password with 13859 queries.
13 Correct 306 ms 720 KB Guessed the password with 18650 queries.
14 Correct 372 ms 700 KB Guessed the password with 19036 queries.
15 Correct 390 ms 716 KB Guessed the password with 18604 queries.
16 Correct 401 ms 720 KB Guessed the password with 18774 queries.
17 Runtime error 325 ms 744 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -