oj.uz

Submission #722698

# Submission time Handle Problem Language Result Execution time Memory
722698 2023-04-12T16:45:13 Z groshi Password (RMI18_password) C++17
100 / 100
 354 ms 496 KB 
#include<bits/stdc++.h>

using namespace std;
int query(string str);
priority_queue<pair<int,string> > kolejka;
string marge(string a,string b)
{
    string wypisz="";
    int l=0,r=0;
    while(l<a.length() || r<b.length())
    {
        if(l==a.length())
        {
            wypisz+=b[r];
            r++;
            continue;
        }
        if(r==b.length())
        {
            wypisz+=a[l];
            l++;
            continue;
        }
        string posiadam="";
        for(int i=l;i<a.length();i++)
            posiadam+=a[i];
        int ile=query(wypisz+b[r]+posiadam);
        if(ile==wypisz.length()+1+posiadam.length())
        {
            wypisz+=b[r];
            r++;
            continue;
        }
        else{
            wypisz+=a[l];
            l++;
            continue;
        }
    }
    return wypisz;
}
string guess(int n,int s)
{
    for(int i=0;i<s;i++)
    {
        string pom="";
        for(int j=1;j<=n;j++)
            pom+=(char)('a'+i);
        int ile=query(pom);
        string mam="";
        for(int j=1;j<=ile;j++)
            mam+=(char)('a'+i);
        if(ile!=0)
            kolejka.push({-ile,mam});
    }
    while(kolejka.size()>=2)
    {
        auto para1=kolejka.top();
        kolejka.pop();
        auto para2=kolejka.top();
        kolejka.pop();
        string mam=marge(para1.second,para2.second);
        kolejka.push({-mam.length(),mam});
    }
    return kolejka.top().second;
}

Compilation message

password.cpp: In function 'std::string marge(std::string, std::string)':
password.cpp:10:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     while(l<a.length() || r<b.length())
      |           ~^~~~~~~~~~~
password.cpp:10:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     while(l<a.length() || r<b.length())
      |                           ~^~~~~~~~~~~
password.cpp:12:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         if(l==a.length())
      |            ~^~~~~~~~~~~~
password.cpp:18:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if(r==b.length())
      |            ~^~~~~~~~~~~~
password.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int i=l;i<a.length();i++)
      |                     ~^~~~~~~~~~~
password.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         if(ile==wypisz.length()+1+posiadam.length())
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 48 queries.
2 Correct 2 ms 208 KB Guessed the password with 91 queries.
3 Correct 2 ms 256 KB Guessed the password with 91 queries.
4 Correct 2 ms 208 KB Guessed the password with 179 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 328 KB Guessed the password with 2751 queries.
2 Correct 31 ms 300 KB Guessed the password with 5071 queries.
3 Correct 61 ms 344 KB Guessed the password with 4585 queries.
4 Correct 90 ms 424 KB Guessed the password with 8086 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 58 queries.
2 Correct 1 ms 208 KB Guessed the password with 102 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 91 queries.
5 Correct 2 ms 256 KB Guessed the password with 91 queries.
6 Correct 2 ms 208 KB Guessed the password with 179 queries.
7 Correct 30 ms 328 KB Guessed the password with 2751 queries.
8 Correct 31 ms 300 KB Guessed the password with 5071 queries.
9 Correct 61 ms 344 KB Guessed the password with 4585 queries.
10 Correct 90 ms 424 KB Guessed the password with 8086 queries.
11 Correct 105 ms 444 KB Guessed the password with 8155 queries.
12 Correct 106 ms 312 KB Guessed the password with 8161 queries.
13 Correct 140 ms 460 KB Guessed the password with 11501 queries.
14 Correct 121 ms 340 KB Guessed the password with 11603 queries.
15 Correct 127 ms 348 KB Guessed the password with 10879 queries.
16 Correct 171 ms 440 KB Guessed the password with 10861 queries.
17 Correct 102 ms 344 KB Guessed the password with 10210 queries.
18 Correct 105 ms 440 KB Guessed the password with 10244 queries.
19 Correct 112 ms 348 KB Guessed the password with 9686 queries.
20 Correct 130 ms 340 KB Guessed the password with 9779 queries.
21 Correct 164 ms 344 KB Guessed the password with 11642 queries.
22 Correct 155 ms 348 KB Guessed the password with 11707 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 58 queries.
2 Correct 1 ms 208 KB Guessed the password with 102 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 91 queries.
5 Correct 2 ms 256 KB Guessed the password with 91 queries.
6 Correct 2 ms 208 KB Guessed the password with 179 queries.
7 Correct 30 ms 328 KB Guessed the password with 2751 queries.
8 Correct 31 ms 300 KB Guessed the password with 5071 queries.
9 Correct 61 ms 344 KB Guessed the password with 4585 queries.
10 Correct 90 ms 424 KB Guessed the password with 8086 queries.
11 Correct 105 ms 444 KB Guessed the password with 8155 queries.
12 Correct 106 ms 312 KB Guessed the password with 8161 queries.
13 Correct 140 ms 460 KB Guessed the password with 11501 queries.
14 Correct 121 ms 340 KB Guessed the password with 11603 queries.
15 Correct 127 ms 348 KB Guessed the password with 10879 queries.
16 Correct 171 ms 440 KB Guessed the password with 10861 queries.
17 Correct 102 ms 344 KB Guessed the password with 10210 queries.
18 Correct 105 ms 440 KB Guessed the password with 10244 queries.
19 Correct 112 ms 348 KB Guessed the password with 9686 queries.
20 Correct 130 ms 340 KB Guessed the password with 9779 queries.
21 Correct 164 ms 344 KB Guessed the password with 11642 queries.
22 Correct 155 ms 348 KB Guessed the password with 11707 queries.
23 Correct 354 ms 400 KB Guessed the password with 23636 queries.
24 Correct 302 ms 384 KB Guessed the password with 20966 queries.
25 Correct 321 ms 496 KB Guessed the password with 23668 queries.
26 Correct 239 ms 384 KB Guessed the password with 19098 queries.
27 Correct 273 ms 376 KB Guessed the password with 23719 queries.
28 Correct 245 ms 420 KB Guessed the password with 16822 queries.
29 Correct 287 ms 384 KB Guessed the password with 23714 queries.
30 Correct 214 ms 372 KB Guessed the password with 14391 queries.