oj.uz

Submission #496357

# Submission time Handle Problem Language Result Execution time Memory
496357 2021-12-21T06:18:43 Z triplem5ds Password (RMI18_password) C++14
100 / 100
 294 ms 516 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) {
    for(int i = s1.size(); i > 0 && s2.size(); --i) {
        for(int j = 1; j <= s2.size() + 1; j++) {
            if(j > s2.size() || 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 cur2 = pq.top().second; pq.pop();
        auto cur1 = 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:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int j = 1; j <= s2.size() + 1; j++) {
      |                        ~~^~~~~~~~~~~~~~~~
password.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             if(j > s2.size() || query(s1.substr(0,i) + s2.substr(s2.size()-j) + s1.substr(i)) != s1.size() + j) {
      |                ~~^~~~~~~~~~~
password.cpp:37:95: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             if(j > s2.size() || 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 2 ms 200 KB Guessed the password with 91 queries.
3 Correct 1 ms 200 KB Guessed the password with 17 queries.
4 Correct 3 ms 292 KB Guessed the password with 174 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 312 KB Guessed the password with 2758 queries.
2 Correct 55 ms 320 KB Guessed the password with 5082 queries.
3 Correct 50 ms 300 KB Guessed the password with 4585 queries.
4 Correct 85 ms 360 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 2 ms 200 KB Guessed the password with 91 queries.
5 Correct 1 ms 200 KB Guessed the password with 17 queries.
6 Correct 3 ms 292 KB Guessed the password with 174 queries.
7 Correct 29 ms 312 KB Guessed the password with 2758 queries.
8 Correct 55 ms 320 KB Guessed the password with 5082 queries.
9 Correct 50 ms 300 KB Guessed the password with 4585 queries.
10 Correct 85 ms 360 KB Guessed the password with 8127 queries.
11 Correct 75 ms 364 KB Guessed the password with 8154 queries.
12 Correct 102 ms 364 KB Guessed the password with 8162 queries.
13 Correct 73 ms 364 KB Guessed the password with 11519 queries.
14 Correct 143 ms 292 KB Guessed the password with 11655 queries.
15 Correct 57 ms 348 KB Guessed the password with 10874 queries.
16 Correct 121 ms 352 KB Guessed the password with 10858 queries.
17 Correct 121 ms 360 KB Guessed the password with 10217 queries.
18 Correct 119 ms 320 KB Guessed the password with 10244 queries.
19 Correct 116 ms 328 KB Guessed the password with 9687 queries.
20 Correct 98 ms 368 KB Guessed the password with 9781 queries.
21 Correct 115 ms 376 KB Guessed the password with 11726 queries.
22 Correct 159 ms 368 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 2 ms 200 KB Guessed the password with 91 queries.
5 Correct 1 ms 200 KB Guessed the password with 17 queries.
6 Correct 3 ms 292 KB Guessed the password with 174 queries.
7 Correct 29 ms 312 KB Guessed the password with 2758 queries.
8 Correct 55 ms 320 KB Guessed the password with 5082 queries.
9 Correct 50 ms 300 KB Guessed the password with 4585 queries.
10 Correct 85 ms 360 KB Guessed the password with 8127 queries.
11 Correct 75 ms 364 KB Guessed the password with 8154 queries.
12 Correct 102 ms 364 KB Guessed the password with 8162 queries.
13 Correct 73 ms 364 KB Guessed the password with 11519 queries.
14 Correct 143 ms 292 KB Guessed the password with 11655 queries.
15 Correct 57 ms 348 KB Guessed the password with 10874 queries.
16 Correct 121 ms 352 KB Guessed the password with 10858 queries.
17 Correct 121 ms 360 KB Guessed the password with 10217 queries.
18 Correct 119 ms 320 KB Guessed the password with 10244 queries.
19 Correct 116 ms 328 KB Guessed the password with 9687 queries.
20 Correct 98 ms 368 KB Guessed the password with 9781 queries.
21 Correct 115 ms 376 KB Guessed the password with 11726 queries.
22 Correct 159 ms 368 KB Guessed the password with 11781 queries.
23 Correct 273 ms 396 KB Guessed the password with 23693 queries.
24 Correct 294 ms 400 KB Guessed the password with 20946 queries.
25 Correct 283 ms 400 KB Guessed the password with 23704 queries.
26 Correct 191 ms 500 KB Guessed the password with 19106 queries.
27 Correct 252 ms 516 KB Guessed the password with 23732 queries.
28 Correct 159 ms 492 KB Guessed the password with 16827 queries.
29 Correct 209 ms 516 KB Guessed the password with 23693 queries.
30 Correct 134 ms 384 KB Guessed the password with 14390 queries.