oj.uz

Submission #1118968

# Submission time Handle Problem Language Result Execution time Memory
1118968 2024-11-26T12:45:56 Z somefolk Password (RMI18_password) C++14
100 / 100
 933 ms 1724 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);

        // for(auto &i : a){
        //     cout << i << " ";
        // }
        // cout << endl;

        // 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)) == sol.size() +  mp[prev] + 1){
                    adj[prev] = j;
                    prev = j;
                } else {
                    adj[j] = prev;
                }
            }
        }

        // for(auto &i : adj){
        //     cout << i.second << "<-" << i.first << endl;
        // }

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

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

        // cout << end << endl;

        // 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++;
            }
        }

        // cout << endl;

        // for(auto &i : adj){
        //     cout << i.second << "<-" << i.first << endl;
        // }

        a.clear();
        a = dis;
    }

    return sol;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:65:60: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                 if(query(sol + j + string(mp[prev], prev)) == sol.size() +  mp[prev] + 1){
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 49 queries.
2 Correct 4 ms 336 KB Guessed the password with 110 queries.
3 Correct 4 ms 336 KB Guessed the password with 92 queries.
4 Correct 5 ms 336 KB Guessed the password with 207 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 716 KB Guessed the password with 3778 queries.
2 Correct 111 ms 696 KB Guessed the password with 5036 queries.
3 Correct 175 ms 696 KB Guessed the password with 7514 queries.
4 Correct 248 ms 720 KB Guessed the password with 12201 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 70 queries.
2 Correct 3 ms 504 KB Guessed the password with 142 queries.
3 Correct 2 ms 336 KB Guessed the password with 49 queries.
4 Correct 4 ms 336 KB Guessed the password with 110 queries.
5 Correct 4 ms 336 KB Guessed the password with 92 queries.
6 Correct 5 ms 336 KB Guessed the password with 207 queries.
7 Correct 94 ms 716 KB Guessed the password with 3778 queries.
8 Correct 111 ms 696 KB Guessed the password with 5036 queries.
9 Correct 175 ms 696 KB Guessed the password with 7514 queries.
10 Correct 248 ms 720 KB Guessed the password with 12201 queries.
11 Correct 295 ms 712 KB Guessed the password with 13733 queries.
12 Correct 313 ms 712 KB Guessed the password with 13488 queries.
13 Correct 414 ms 972 KB Guessed the password with 18177 queries.
14 Correct 423 ms 488 KB Guessed the password with 18819 queries.
15 Correct 412 ms 960 KB Guessed the password with 18402 queries.
16 Correct 414 ms 720 KB Guessed the password with 18296 queries.
17 Correct 367 ms 952 KB Guessed the password with 15493 queries.
18 Correct 365 ms 704 KB Guessed the password with 15720 queries.
19 Correct 343 ms 592 KB Guessed the password with 15794 queries.
20 Correct 341 ms 716 KB Guessed the password with 15397 queries.
21 Correct 306 ms 716 KB Guessed the password with 12313 queries.
22 Correct 294 ms 492 KB Guessed the password with 11557 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 70 queries.
2 Correct 3 ms 504 KB Guessed the password with 142 queries.
3 Correct 2 ms 336 KB Guessed the password with 49 queries.
4 Correct 4 ms 336 KB Guessed the password with 110 queries.
5 Correct 4 ms 336 KB Guessed the password with 92 queries.
6 Correct 5 ms 336 KB Guessed the password with 207 queries.
7 Correct 94 ms 716 KB Guessed the password with 3778 queries.
8 Correct 111 ms 696 KB Guessed the password with 5036 queries.
9 Correct 175 ms 696 KB Guessed the password with 7514 queries.
10 Correct 248 ms 720 KB Guessed the password with 12201 queries.
11 Correct 295 ms 712 KB Guessed the password with 13733 queries.
12 Correct 313 ms 712 KB Guessed the password with 13488 queries.
13 Correct 414 ms 972 KB Guessed the password with 18177 queries.
14 Correct 423 ms 488 KB Guessed the password with 18819 queries.
15 Correct 412 ms 960 KB Guessed the password with 18402 queries.
16 Correct 414 ms 720 KB Guessed the password with 18296 queries.
17 Correct 367 ms 952 KB Guessed the password with 15493 queries.
18 Correct 365 ms 704 KB Guessed the password with 15720 queries.
19 Correct 343 ms 592 KB Guessed the password with 15794 queries.
20 Correct 341 ms 716 KB Guessed the password with 15397 queries.
21 Correct 306 ms 716 KB Guessed the password with 12313 queries.
22 Correct 294 ms 492 KB Guessed the password with 11557 queries.
23 Correct 601 ms 1392 KB Guessed the password with 25515 queries.
24 Correct 499 ms 984 KB Guessed the password with 21826 queries.
25 Correct 859 ms 1724 KB Guessed the password with 38155 queries.
26 Correct 696 ms 1520 KB Guessed the password with 30101 queries.
27 Correct 909 ms 1436 KB Guessed the password with 40656 queries.
28 Correct 629 ms 1232 KB Guessed the password with 27724 queries.
29 Correct 933 ms 1248 KB Guessed the password with 43434 queries.
30 Correct 545 ms 1432 KB Guessed the password with 23653 queries.