oj.uz

Submission #496350

# Submission time Handle Problem Language Result Execution time Memory
496350 2021-12-21T06:13:54 Z triplem5ds Password (RMI18_password) C++14
100 / 100
 258 ms 684 KB 
/// Zengy MANGA
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include "bits/stdc++.h"

using namespace std;

#define pb push_back
#define F first
#define S second
#define f(i, a, b)  for(int i = a; i < b; i++)
#define all(a)  a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) (int)(x).size()
#define mp(x,y) make_pair(x,y)
#define popCnt(x) (__builtin_popcountll(x))

using ll = long long;
using ii = pair<int,int>;
using ull = unsigned long long;
using db = long double;

const int N = 2e5+5, LG = 18, MOD = 998244353;
const long double PI = acos(-1);

int query(string s);

using is = pair<int, string>;

priority_queue<is, vector<is>, greater<is>> pq;

string mrg(string s1, string s2) {
    swap(s2,s1);
    for(int i = s1.size(); i > 0 && s2.size(); --i) {
        for(int j = 1; j <= s2.size() + 1; j++) {
            if(j > s2.size()) {
                s1 = s1.substr(0,i) + s2 + s1.substr(i);
                s2 = "";
                break;
            }
            if(query(s1.substr(0,i) + s2.substr(s2.size()-j) + s1.substr(i)) != s1.size() + j) {
                s1 = s1.substr(0,i) + s2.substr(s2.size()-(j-1)) + s1.substr(i);
                f(k,0,j-1)s2.pop_back();
                break;
            }
        }
    }
    return s2+s1;
}

string guess(int n, int s) {

    f(i,0,s) {
        string str = string(query(string(n, 'a' + i)), 'a' + i);
        if(str.size())
        pq.push(make_pair(str.size(), str));
    }

    while(sz(pq) > 1) {

        auto cur1 = pq.top().second; pq.pop();
        auto cur2 = pq.top().second; pq.pop();

        string ans = mrg(cur1, cur2);

        pq.push(mp(sz(ans), ans));
    }

    return pq.top().second;
}

Compilation message

password.cpp: In function 'std::string mrg(std::string, std::string)':
password.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j = 1; j <= s2.size() + 1; j++) {
      |                        ~~^~~~~~~~~~~~~~~~
password.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             if(j > s2.size()) {
      |                ~~^~~~~~~~~~~
password.cpp:43:78: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             if(query(s1.substr(0,i) + s2.substr(s2.size()-j) + s1.substr(i)) != s1.size() + j) {
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 58 queries.
2 Correct 2 ms 200 KB Guessed the password with 100 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 47 queries.
2 Correct 1 ms 200 KB Guessed the password with 91 queries.
3 Correct 0 ms 200 KB Guessed the password with 17 queries.
4 Correct 2 ms 200 KB Guessed the password with 174 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 292 KB Guessed the password with 2758 queries.
2 Correct 73 ms 312 KB Guessed the password with 5082 queries.
3 Correct 34 ms 464 KB Guessed the password with 4585 queries.
4 Correct 69 ms 344 KB Guessed the password with 8127 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 58 queries.
2 Correct 2 ms 200 KB Guessed the password with 100 queries.
3 Correct 1 ms 200 KB Guessed the password with 47 queries.
4 Correct 1 ms 200 KB Guessed the password with 91 queries.
5 Correct 0 ms 200 KB Guessed the password with 17 queries.
6 Correct 2 ms 200 KB Guessed the password with 174 queries.
7 Correct 29 ms 292 KB Guessed the password with 2758 queries.
8 Correct 73 ms 312 KB Guessed the password with 5082 queries.
9 Correct 34 ms 464 KB Guessed the password with 4585 queries.
10 Correct 69 ms 344 KB Guessed the password with 8127 queries.
11 Correct 89 ms 552 KB Guessed the password with 8154 queries.
12 Correct 45 ms 472 KB Guessed the password with 8162 queries.
13 Correct 159 ms 496 KB Guessed the password with 11519 queries.
14 Correct 119 ms 416 KB Guessed the password with 11655 queries.
15 Correct 105 ms 372 KB Guessed the password with 10874 queries.
16 Correct 94 ms 488 KB Guessed the password with 10858 queries.
17 Correct 97 ms 364 KB Guessed the password with 10217 queries.
18 Correct 105 ms 368 KB Guessed the password with 10244 queries.
19 Correct 114 ms 492 KB Guessed the password with 9687 queries.
20 Correct 103 ms 364 KB Guessed the password with 9781 queries.
21 Correct 132 ms 372 KB Guessed the password with 11726 queries.
22 Correct 130 ms 360 KB Guessed the password with 11781 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 58 queries.
2 Correct 2 ms 200 KB Guessed the password with 100 queries.
3 Correct 1 ms 200 KB Guessed the password with 47 queries.
4 Correct 1 ms 200 KB Guessed the password with 91 queries.
5 Correct 0 ms 200 KB Guessed the password with 17 queries.
6 Correct 2 ms 200 KB Guessed the password with 174 queries.
7 Correct 29 ms 292 KB Guessed the password with 2758 queries.
8 Correct 73 ms 312 KB Guessed the password with 5082 queries.
9 Correct 34 ms 464 KB Guessed the password with 4585 queries.
10 Correct 69 ms 344 KB Guessed the password with 8127 queries.
11 Correct 89 ms 552 KB Guessed the password with 8154 queries.
12 Correct 45 ms 472 KB Guessed the password with 8162 queries.
13 Correct 159 ms 496 KB Guessed the password with 11519 queries.
14 Correct 119 ms 416 KB Guessed the password with 11655 queries.
15 Correct 105 ms 372 KB Guessed the password with 10874 queries.
16 Correct 94 ms 488 KB Guessed the password with 10858 queries.
17 Correct 97 ms 364 KB Guessed the password with 10217 queries.
18 Correct 105 ms 368 KB Guessed the password with 10244 queries.
19 Correct 114 ms 492 KB Guessed the password with 9687 queries.
20 Correct 103 ms 364 KB Guessed the password with 9781 queries.
21 Correct 132 ms 372 KB Guessed the password with 11726 queries.
22 Correct 130 ms 360 KB Guessed the password with 11781 queries.
23 Correct 225 ms 396 KB Guessed the password with 23693 queries.
24 Correct 212 ms 572 KB Guessed the password with 20946 queries.
25 Correct 213 ms 444 KB Guessed the password with 23704 queries.
26 Correct 162 ms 512 KB Guessed the password with 19106 queries.
27 Correct 258 ms 684 KB Guessed the password with 23732 queries.
28 Correct 179 ms 432 KB Guessed the password with 16827 queries.
29 Correct 248 ms 472 KB Guessed the password with 23693 queries.
30 Correct 122 ms 504 KB Guessed the password with 14390 queries.