oj.uz

Submission #1117386

# Submission time Handle Problem Language Result Execution time Memory
1117386 2024-11-23T13:27:18 Z somefolk Password (RMI18_password) C++14
50 / 100
 1047 ms 964 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>
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){
    map<char, int> a;
    for(char i = 0; i < s; i++){
        string s1 = string(n, i+'a');
        a[i+'a'] = query(s1);
    }

    string sol = "";
    for(int i = 0; i < n; i++){
        char prev;
        for(auto &j : a){
            if(j.second != 0){
                prev = j.first;
                break;
            }
        }
        for(auto &j : a){
            if(prev == j.first || j.second == 0) continue;
            if(query(sol + j.first + string(a[prev], prev)) == sol.size() + a[prev] + 1){
                prev = j.first;
            }
        }
        a[prev]--;
        sol+=prev;
    }

    return sol;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Guessed the password with 120 queries.
2 Correct 5 ms 336 KB Guessed the password with 276 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 132 queries.
3 Correct 4 ms 336 KB Guessed the password with 170 queries.
4 Correct 5 ms 592 KB Guessed the password with 293 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 700 KB Guessed the password with 9608 queries.
2 Correct 346 ms 688 KB Guessed the password with 17344 queries.
3 Correct 457 ms 688 KB Guessed the password with 21757 queries.
4 Correct 758 ms 848 KB Guessed the password with 36499 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Guessed the password with 120 queries.
2 Correct 5 ms 336 KB Guessed the password with 276 queries.
3 Correct 1 ms 336 KB Guessed the password with 48 queries.
4 Correct 3 ms 336 KB Guessed the password with 132 queries.
5 Correct 4 ms 336 KB Guessed the password with 170 queries.
6 Correct 5 ms 592 KB Guessed the password with 293 queries.
7 Correct 185 ms 700 KB Guessed the password with 9608 queries.
8 Correct 346 ms 688 KB Guessed the password with 17344 queries.
9 Correct 457 ms 688 KB Guessed the password with 21757 queries.
10 Correct 758 ms 848 KB Guessed the password with 36499 queries.
11 Incorrect 1047 ms 964 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Guessed the password with 120 queries.
2 Correct 5 ms 336 KB Guessed the password with 276 queries.
3 Correct 1 ms 336 KB Guessed the password with 48 queries.
4 Correct 3 ms 336 KB Guessed the password with 132 queries.
5 Correct 4 ms 336 KB Guessed the password with 170 queries.
6 Correct 5 ms 592 KB Guessed the password with 293 queries.
7 Correct 185 ms 700 KB Guessed the password with 9608 queries.
8 Correct 346 ms 688 KB Guessed the password with 17344 queries.
9 Correct 457 ms 688 KB Guessed the password with 21757 queries.
10 Correct 758 ms 848 KB Guessed the password with 36499 queries.
11 Incorrect 1047 ms 964 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -