oj.uz

Submission #1119117

# Submission time Handle Problem Language Result Execution time Memory
1119117 2024-11-26T16:09:26 Z somefolk Password (RMI18_password) C++17
50 / 100
 388 ms 968 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);

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)) == 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;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:53:60: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                 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 63 queries.
2 Correct 4 ms 444 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 4 ms 340 KB Guessed the password with 92 queries.
4 Correct 5 ms 336 KB Guessed the password with 204 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 724 KB Guessed the password with 3825 queries.
2 Correct 110 ms 724 KB Guessed the password with 4970 queries.
3 Correct 158 ms 592 KB Guessed the password with 7586 queries.
4 Correct 253 ms 712 KB Guessed the password with 11976 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 63 queries.
2 Correct 4 ms 444 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 4 ms 340 KB Guessed the password with 92 queries.
6 Correct 5 ms 336 KB Guessed the password with 204 queries.
7 Correct 77 ms 724 KB Guessed the password with 3825 queries.
8 Correct 110 ms 724 KB Guessed the password with 4970 queries.
9 Correct 158 ms 592 KB Guessed the password with 7586 queries.
10 Correct 253 ms 712 KB Guessed the password with 11976 queries.
11 Correct 336 ms 968 KB Guessed the password with 13981 queries.
12 Correct 243 ms 492 KB Guessed the password with 13572 queries.
13 Correct 388 ms 488 KB Guessed the password with 18897 queries.
14 Runtime error 377 ms 752 KB Execution killed with signal 13
15 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 63 queries.
2 Correct 4 ms 444 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 4 ms 340 KB Guessed the password with 92 queries.
6 Correct 5 ms 336 KB Guessed the password with 204 queries.
7 Correct 77 ms 724 KB Guessed the password with 3825 queries.
8 Correct 110 ms 724 KB Guessed the password with 4970 queries.
9 Correct 158 ms 592 KB Guessed the password with 7586 queries.
10 Correct 253 ms 712 KB Guessed the password with 11976 queries.
11 Correct 336 ms 968 KB Guessed the password with 13981 queries.
12 Correct 243 ms 492 KB Guessed the password with 13572 queries.
13 Correct 388 ms 488 KB Guessed the password with 18897 queries.
14 Runtime error 377 ms 752 KB Execution killed with signal 13
15 Halted 0 ms 0 KB -