oj.uz

Submission #1111195

# Submission time Handle Problem Language Result Execution time Memory
1111195 2024-11-11T16:58:48 Z sofija6 Password (RMI18_password) C++14
100 / 100
 548 ms 1976 KB 
#include <bits/stdc++.h>

using namespace std;

int query(string q);

string Merge(string a,string b)
{
    int posa=0,posb=0;
    string ans="";
    while (posa<a.size() && posb<b.size())
    {
        string d=ans;
        d+=a[posa];
        for (int j=posb;j<b.size();j++)
            d+=(char)b[j];
        if (query(d)==(int)d.size())
        {
            ans+=a[posa];
            posa++;
        }
        else
        {
            ans+=b[posb];
            posb++;
        }
    }
    for (int i=posa;i<a.size();i++)
        ans+=a[i];
    for (int i=posb;i<b.size();i++)
        ans+=b[i];
    return ans;
}
bool Cmp(string a,string b)
{
    return a.size()<b.size();
}
string guess(int n, int s)
{
    vector<string> cur,cur1;
    for (int i=0;i<s;i++)
    {
        string ss="";
        for (int j=0;j<n;j++)
            ss+=(char)('a'+i);
        int len=query(ss);
        if (len)
        {
            ss="";
            for (int j=0;j<len;j++)
                ss+=(char)('a'+i);
            cur.push_back(ss);
        }
    }
    while (cur.size()!=1)
    {
        sort(cur.begin(),cur.end(),Cmp);
        string a=cur[0],b=cur[1];
        for (int i=2;i<cur.size();i++)
            cur1.push_back(cur[i]);
        cur=cur1;
        cur1.clear();
        cur.push_back(Merge(a,b));
    }
    return cur[0];
}

Compilation message

password.cpp: In function 'std::string Merge(std::string, std::string)':
password.cpp:11:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     while (posa<a.size() && posb<b.size())
      |            ~~~~^~~~~~~~~
password.cpp:11:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     while (posa<a.size() && posb<b.size())
      |                             ~~~~^~~~~~~~~
password.cpp:15:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for (int j=posb;j<b.size();j++)
      |                         ~^~~~~~~~~
password.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i=posa;i<a.size();i++)
      |                     ~^~~~~~~~~
password.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i=posb;i<b.size();i++)
      |                     ~^~~~~~~~~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int i=2;i<cur.size();i++)
      |                      ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Guessed the password with 58 queries.
2 Correct 2 ms 336 KB Guessed the password with 99 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Guessed the password with 49 queries.
2 Correct 2 ms 336 KB Guessed the password with 90 queries.
3 Correct 2 ms 336 KB Guessed the password with 92 queries.
4 Correct 4 ms 336 KB Guessed the password with 178 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 716 KB Guessed the password with 2750 queries.
2 Correct 107 ms 736 KB Guessed the password with 5070 queries.
3 Correct 102 ms 704 KB Guessed the password with 4585 queries.
4 Correct 150 ms 752 KB Guessed the password with 8085 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Guessed the password with 58 queries.
2 Correct 2 ms 336 KB Guessed the password with 99 queries.
3 Correct 2 ms 336 KB Guessed the password with 49 queries.
4 Correct 2 ms 336 KB Guessed the password with 90 queries.
5 Correct 2 ms 336 KB Guessed the password with 92 queries.
6 Correct 4 ms 336 KB Guessed the password with 178 queries.
7 Correct 51 ms 716 KB Guessed the password with 2750 queries.
8 Correct 107 ms 736 KB Guessed the password with 5070 queries.
9 Correct 102 ms 704 KB Guessed the password with 4585 queries.
10 Correct 150 ms 752 KB Guessed the password with 8085 queries.
11 Correct 165 ms 964 KB Guessed the password with 8159 queries.
12 Correct 166 ms 764 KB Guessed the password with 8161 queries.
13 Correct 247 ms 740 KB Guessed the password with 11501 queries.
14 Correct 247 ms 848 KB Guessed the password with 11601 queries.
15 Correct 223 ms 980 KB Guessed the password with 10880 queries.
16 Correct 228 ms 980 KB Guessed the password with 10860 queries.
17 Correct 217 ms 840 KB Guessed the password with 10209 queries.
18 Correct 226 ms 988 KB Guessed the password with 10247 queries.
19 Correct 220 ms 700 KB Guessed the password with 9687 queries.
20 Correct 226 ms 764 KB Guessed the password with 9772 queries.
21 Correct 239 ms 764 KB Guessed the password with 11641 queries.
22 Correct 253 ms 1016 KB Guessed the password with 11709 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Guessed the password with 58 queries.
2 Correct 2 ms 336 KB Guessed the password with 99 queries.
3 Correct 2 ms 336 KB Guessed the password with 49 queries.
4 Correct 2 ms 336 KB Guessed the password with 90 queries.
5 Correct 2 ms 336 KB Guessed the password with 92 queries.
6 Correct 4 ms 336 KB Guessed the password with 178 queries.
7 Correct 51 ms 716 KB Guessed the password with 2750 queries.
8 Correct 107 ms 736 KB Guessed the password with 5070 queries.
9 Correct 102 ms 704 KB Guessed the password with 4585 queries.
10 Correct 150 ms 752 KB Guessed the password with 8085 queries.
11 Correct 165 ms 964 KB Guessed the password with 8159 queries.
12 Correct 166 ms 764 KB Guessed the password with 8161 queries.
13 Correct 247 ms 740 KB Guessed the password with 11501 queries.
14 Correct 247 ms 848 KB Guessed the password with 11601 queries.
15 Correct 223 ms 980 KB Guessed the password with 10880 queries.
16 Correct 228 ms 980 KB Guessed the password with 10860 queries.
17 Correct 217 ms 840 KB Guessed the password with 10209 queries.
18 Correct 226 ms 988 KB Guessed the password with 10247 queries.
19 Correct 220 ms 700 KB Guessed the password with 9687 queries.
20 Correct 226 ms 764 KB Guessed the password with 9772 queries.
21 Correct 239 ms 764 KB Guessed the password with 11641 queries.
22 Correct 253 ms 1016 KB Guessed the password with 11709 queries.
23 Correct 523 ms 976 KB Guessed the password with 23650 queries.
24 Correct 462 ms 776 KB Guessed the password with 20965 queries.
25 Correct 510 ms 1976 KB Guessed the password with 23670 queries.
26 Correct 438 ms 1748 KB Guessed the password with 19099 queries.
27 Correct 548 ms 852 KB Guessed the password with 23703 queries.
28 Correct 389 ms 772 KB Guessed the password with 16823 queries.
29 Correct 529 ms 840 KB Guessed the password with 23714 queries.
30 Correct 347 ms 752 KB Guessed the password with 14391 queries.