oj.uz

Submission #496348

# Submission time Handle Problem Language Result Execution time Memory
496348 2021-12-21T06:10:53 Z triplem5ds Password (RMI18_password) C++14
80 / 100
 232 ms 544 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()) {
                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: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()) {
      |                ~~^~~~~~~~~~~
password.cpp:42:78: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             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 59 queries.
2 Correct 1 ms 200 KB Guessed the password with 99 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 48 queries.
2 Correct 1 ms 200 KB Guessed the password with 92 queries.
3 Correct 1 ms 200 KB Guessed the password with 18 queries.
4 Correct 2 ms 200 KB Guessed the password with 175 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 340 KB Guessed the password with 2757 queries.
2 Correct 23 ms 292 KB Guessed the password with 5083 queries.
3 Correct 41 ms 304 KB Guessed the password with 4586 queries.
4 Correct 82 ms 452 KB Guessed the password with 8128 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 59 queries.
2 Correct 1 ms 200 KB Guessed the password with 99 queries.
3 Correct 1 ms 200 KB Guessed the password with 48 queries.
4 Correct 1 ms 200 KB Guessed the password with 92 queries.
5 Correct 1 ms 200 KB Guessed the password with 18 queries.
6 Correct 2 ms 200 KB Guessed the password with 175 queries.
7 Correct 24 ms 340 KB Guessed the password with 2757 queries.
8 Correct 23 ms 292 KB Guessed the password with 5083 queries.
9 Correct 41 ms 304 KB Guessed the password with 4586 queries.
10 Correct 82 ms 452 KB Guessed the password with 8128 queries.
11 Correct 81 ms 356 KB Guessed the password with 8153 queries.
12 Correct 84 ms 296 KB Guessed the password with 8161 queries.
13 Correct 91 ms 360 KB Guessed the password with 11520 queries.
14 Correct 112 ms 368 KB Guessed the password with 11656 queries.
15 Correct 102 ms 476 KB Guessed the password with 10875 queries.
16 Correct 114 ms 452 KB Guessed the password with 10857 queries.
17 Correct 90 ms 348 KB Guessed the password with 10218 queries.
18 Correct 93 ms 428 KB Guessed the password with 10243 queries.
19 Correct 85 ms 360 KB Guessed the password with 9686 queries.
20 Correct 95 ms 448 KB Guessed the password with 9780 queries.
21 Correct 129 ms 440 KB Guessed the password with 11725 queries.
22 Correct 107 ms 544 KB Guessed the password with 11782 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 59 queries.
2 Correct 1 ms 200 KB Guessed the password with 99 queries.
3 Correct 1 ms 200 KB Guessed the password with 48 queries.
4 Correct 1 ms 200 KB Guessed the password with 92 queries.
5 Correct 1 ms 200 KB Guessed the password with 18 queries.
6 Correct 2 ms 200 KB Guessed the password with 175 queries.
7 Correct 24 ms 340 KB Guessed the password with 2757 queries.
8 Correct 23 ms 292 KB Guessed the password with 5083 queries.
9 Correct 41 ms 304 KB Guessed the password with 4586 queries.
10 Correct 82 ms 452 KB Guessed the password with 8128 queries.
11 Correct 81 ms 356 KB Guessed the password with 8153 queries.
12 Correct 84 ms 296 KB Guessed the password with 8161 queries.
13 Correct 91 ms 360 KB Guessed the password with 11520 queries.
14 Correct 112 ms 368 KB Guessed the password with 11656 queries.
15 Correct 102 ms 476 KB Guessed the password with 10875 queries.
16 Correct 114 ms 452 KB Guessed the password with 10857 queries.
17 Correct 90 ms 348 KB Guessed the password with 10218 queries.
18 Correct 93 ms 428 KB Guessed the password with 10243 queries.
19 Correct 85 ms 360 KB Guessed the password with 9686 queries.
20 Correct 95 ms 448 KB Guessed the password with 9780 queries.
21 Correct 129 ms 440 KB Guessed the password with 11725 queries.
22 Correct 107 ms 544 KB Guessed the password with 11782 queries.
23 Runtime error 232 ms 392 KB Execution killed with signal 13
24 Halted 0 ms 0 KB -