oj.uz

Submission #648345

# Submission time Handle Problem Language Result Execution time Memory
648345 2022-10-06T08:15:05 Z tudor Password (RMI18_password) C++17
100 / 100
 230 ms 504 KB 
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string.h>

using namespace std;

priority_queue < pair < int, string > > pq;

int query ( string a );

pair < int, string > comb ( pair < int, string > a, pair < int, string > b ) {
    int n = -a.first, m = -b.first, i = n, j = m - 1;
    vector < int > poz ( n + 2 );
    poz[0] = 0;
    poz[n + 1] = m;
    while ( i >= 1 ) {
        while ( j >= 0 ) {
            string q = a.second.substr ( 0, i ) + b.second.substr ( j );
            if ( query ( q ) < q.size () )
                break;
            j--;
        }
        poz[i] = j + 1;
        i--;
    }
    for ( int i = 0; i <= n; i++ )
        for ( int j = poz[i]; j < poz[i + 1]; j++ )
            a.second.insert ( a.second.begin () + i + j, b.second[j] );

    return { a.first + b.first, a.second };

}

string guess ( int n, int s ) {
    int sum = 0;
    string S;
    for ( int i = 0; i < s - 1; i++ ) {
        int x = query ( string ( n, 'a' + i ) );
        if ( x > 0 )
            pq.push ( { -x, string ( x, 'a' + i ) } );
        sum += x;
    }
    if ( n - sum > 0 )
        pq.push ( { - ( n - sum ), string ( n - sum, 'a' + s - 1 ) } );

    while ( pq.size () > 1 ) {
        pair < int, string > a = pq.top ();
        pq.pop ();
        pair < int, string > b = pq.top ();
        pq.pop ();
        pq.push ( comb ( a, b ) );
    }
    return pq.top ().second;
}

Compilation message

password.cpp: In function 'std::pair<int, std::__cxx11::basic_string<char> > comb(std::pair<int, std::__cxx11::basic_string<char> >, std::pair<int, std::__cxx11::basic_string<char> >)':
password.cpp:21:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             if ( query ( q ) < q.size () )
      |                  ~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 57 queries.
2 Correct 1 ms 208 KB Guessed the password with 104 queries.

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 300 KB Guessed the password with 2757 queries.
2 Correct 53 ms 300 KB Guessed the password with 5083 queries.
3 Correct 36 ms 356 KB Guessed the password with 4586 queries.
4 Correct 77 ms 296 KB Guessed the password with 8125 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 57 queries.
2 Correct 1 ms 208 KB Guessed the password with 104 queries.
3 Correct 1 ms 208 KB Guessed the password with 47 queries.
4 Correct 1 ms 208 KB Guessed the password with 91 queries.
5 Correct 1 ms 208 KB Guessed the password with 17 queries.
6 Correct 4 ms 208 KB Guessed the password with 174 queries.
7 Correct 29 ms 300 KB Guessed the password with 2757 queries.
8 Correct 53 ms 300 KB Guessed the password with 5083 queries.
9 Correct 36 ms 356 KB Guessed the password with 4586 queries.
10 Correct 77 ms 296 KB Guessed the password with 8125 queries.
11 Correct 70 ms 388 KB Guessed the password with 8158 queries.
12 Correct 69 ms 420 KB Guessed the password with 8164 queries.
13 Correct 115 ms 380 KB Guessed the password with 11517 queries.
14 Correct 129 ms 428 KB Guessed the password with 11655 queries.
15 Correct 102 ms 420 KB Guessed the password with 10874 queries.
16 Correct 71 ms 376 KB Guessed the password with 10853 queries.
17 Correct 110 ms 356 KB Guessed the password with 10217 queries.
18 Correct 101 ms 360 KB Guessed the password with 10246 queries.
19 Correct 161 ms 364 KB Guessed the password with 9688 queries.
20 Correct 55 ms 368 KB Guessed the password with 9783 queries.
21 Correct 75 ms 376 KB Guessed the password with 11723 queries.
22 Correct 105 ms 436 KB Guessed the password with 11778 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 57 queries.
2 Correct 1 ms 208 KB Guessed the password with 104 queries.
3 Correct 1 ms 208 KB Guessed the password with 47 queries.
4 Correct 1 ms 208 KB Guessed the password with 91 queries.
5 Correct 1 ms 208 KB Guessed the password with 17 queries.
6 Correct 4 ms 208 KB Guessed the password with 174 queries.
7 Correct 29 ms 300 KB Guessed the password with 2757 queries.
8 Correct 53 ms 300 KB Guessed the password with 5083 queries.
9 Correct 36 ms 356 KB Guessed the password with 4586 queries.
10 Correct 77 ms 296 KB Guessed the password with 8125 queries.
11 Correct 70 ms 388 KB Guessed the password with 8158 queries.
12 Correct 69 ms 420 KB Guessed the password with 8164 queries.
13 Correct 115 ms 380 KB Guessed the password with 11517 queries.
14 Correct 129 ms 428 KB Guessed the password with 11655 queries.
15 Correct 102 ms 420 KB Guessed the password with 10874 queries.
16 Correct 71 ms 376 KB Guessed the password with 10853 queries.
17 Correct 110 ms 356 KB Guessed the password with 10217 queries.
18 Correct 101 ms 360 KB Guessed the password with 10246 queries.
19 Correct 161 ms 364 KB Guessed the password with 9688 queries.
20 Correct 55 ms 368 KB Guessed the password with 9783 queries.
21 Correct 75 ms 376 KB Guessed the password with 11723 queries.
22 Correct 105 ms 436 KB Guessed the password with 11778 queries.
23 Correct 230 ms 396 KB Guessed the password with 23693 queries.
24 Correct 155 ms 484 KB Guessed the password with 20942 queries.
25 Correct 213 ms 504 KB Guessed the password with 23693 queries.
26 Correct 191 ms 404 KB Guessed the password with 19104 queries.
27 Correct 196 ms 392 KB Guessed the password with 23731 queries.
28 Correct 163 ms 488 KB Guessed the password with 16827 queries.
29 Correct 156 ms 464 KB Guessed the password with 23690 queries.
30 Correct 115 ms 440 KB Guessed the password with 14391 queries.