oj.uz

Submission #1118977

# Submission time Handle Problem Language Result Execution time Memory
1118977 2024-11-26T12:49:09 Z somefolk Password (RMI18_password) C++14
80 / 100
 996 ms 1512 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)) == 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:60:60: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                 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 80 queries.
2 Correct 3 ms 440 KB Guessed the password with 134 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Guessed the password with 48 queries.
2 Correct 3 ms 336 KB Guessed the password with 107 queries.
3 Correct 2 ms 336 KB Guessed the password with 92 queries.
4 Correct 5 ms 592 KB Guessed the password with 234 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 708 KB Guessed the password with 4448 queries.
2 Correct 140 ms 688 KB Guessed the password with 6939 queries.
3 Correct 190 ms 716 KB Guessed the password with 10042 queries.
4 Correct 263 ms 700 KB Guessed the password with 13403 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 440 KB Guessed the password with 134 queries.
3 Correct 1 ms 336 KB Guessed the password with 48 queries.
4 Correct 3 ms 336 KB Guessed the password with 107 queries.
5 Correct 2 ms 336 KB Guessed the password with 92 queries.
6 Correct 5 ms 592 KB Guessed the password with 234 queries.
7 Correct 76 ms 708 KB Guessed the password with 4448 queries.
8 Correct 140 ms 688 KB Guessed the password with 6939 queries.
9 Correct 190 ms 716 KB Guessed the password with 10042 queries.
10 Correct 263 ms 700 KB Guessed the password with 13403 queries.
11 Correct 468 ms 480 KB Guessed the password with 23301 queries.
12 Correct 364 ms 488 KB Guessed the password with 19329 queries.
13 Correct 505 ms 688 KB Guessed the password with 25823 queries.
14 Correct 499 ms 708 KB Guessed the password with 25447 queries.
15 Correct 439 ms 592 KB Guessed the password with 23145 queries.
16 Correct 450 ms 696 KB Guessed the password with 23813 queries.
17 Correct 438 ms 700 KB Guessed the password with 21977 queries.
18 Correct 524 ms 480 KB Guessed the password with 26269 queries.
19 Correct 515 ms 724 KB Guessed the password with 26874 queries.
20 Correct 397 ms 724 KB Guessed the password with 20325 queries.
21 Correct 479 ms 592 KB Guessed the password with 25093 queries.
22 Correct 512 ms 740 KB Guessed the password with 25344 queries.

Subtask #5
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 440 KB Guessed the password with 134 queries.
3 Correct 1 ms 336 KB Guessed the password with 48 queries.
4 Correct 3 ms 336 KB Guessed the password with 107 queries.
5 Correct 2 ms 336 KB Guessed the password with 92 queries.
6 Correct 5 ms 592 KB Guessed the password with 234 queries.
7 Correct 76 ms 708 KB Guessed the password with 4448 queries.
8 Correct 140 ms 688 KB Guessed the password with 6939 queries.
9 Correct 190 ms 716 KB Guessed the password with 10042 queries.
10 Correct 263 ms 700 KB Guessed the password with 13403 queries.
11 Correct 468 ms 480 KB Guessed the password with 23301 queries.
12 Correct 364 ms 488 KB Guessed the password with 19329 queries.
13 Correct 505 ms 688 KB Guessed the password with 25823 queries.
14 Correct 499 ms 708 KB Guessed the password with 25447 queries.
15 Correct 439 ms 592 KB Guessed the password with 23145 queries.
16 Correct 450 ms 696 KB Guessed the password with 23813 queries.
17 Correct 438 ms 700 KB Guessed the password with 21977 queries.
18 Correct 524 ms 480 KB Guessed the password with 26269 queries.
19 Correct 515 ms 724 KB Guessed the password with 26874 queries.
20 Correct 397 ms 724 KB Guessed the password with 20325 queries.
21 Correct 479 ms 592 KB Guessed the password with 25093 queries.
22 Correct 512 ms 740 KB Guessed the password with 25344 queries.
23 Correct 996 ms 992 KB Guessed the password with 46261 queries.
24 Correct 857 ms 1512 KB Guessed the password with 43503 queries.
25 Runtime error 929 ms 1504 KB Execution killed with signal 13
26 Halted 0 ms 0 KB -