Submission #648345

#	Time	Username	Problem	Language	Result	Execution time	Memory
648345		tudor	Password (RMI18_password)	C++17	100 / 100	230 ms	504 KiB

password

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20