oj.uz

Submission #641167

# Submission time Handle Problem Language Result Execution time Memory
641167 2022-09-16T06:42:57 Z Tenis0206 Password (RMI18_password) C++14
50 / 100
 450 ms 604 KB 
#include <bits/stdc++.h>

//#define home

using namespace std;

int query(string s);

#ifdef home

string str;

int query(string s)
{
    int j = 0;
    for(int i=0;i<s.size();i++)
    {
        while(j<str.size() && s[i]!=str[j])
        {
            ++j;
        }
        if(j==str.size())
        {
            return i;
        }
        ++j;
    }
    return s.size();
}

#endif // home

string s[205];

string Merge(string a, string b)
{
    int i = 0, j = 0;
    string rez;
    while(i<a.size() && j<b.size())
    {
        string aux = rez + a[i];
        for(int p=j;p<b.size();p++)
        {
            aux.push_back(b[p]);
        }
        int nr = query(aux);
        if(nr==aux.size())
        {
            rez.push_back(a[i]);
            ++i;
        }
        else
        {
            rez.push_back(b[j]);
            ++j;
        }
    }
    while(i<a.size())
    {
        rez.push_back(a[i]);
        ++i;
    }
    while(j<b.size())
    {
        rez.push_back(b[j]);
        ++j;
    }
    return rez;
}

string guess(int n, int cr)
{
    for(int c='a';c<='a'+cr-1;c++)
    {
        string aux;
        for(int j=1;j<=n;j++)
        {
            aux.push_back(c);
        }
        int nr = query(aux);
        for(int j=1;j<=nr;j++)
        {
            s[c].push_back(c);
        }
    }
    string rez;
    for(int c='a';c<='a'+cr-1;c++)
    {
        rez = Merge(rez,s[c]);
    }
    return rez;
}

#ifdef home

int main()
{
    cin>>str;
    cout<<guess(str.size(),4)<<'\n';
    return 0;
}

#endif // home

Compilation message

password.cpp: In function 'std::string Merge(std::string, std::string)':
password.cpp:39:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while(i<a.size() && j<b.size())
      |           ~^~~~~~~~~
password.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while(i<a.size() && j<b.size())
      |                         ~^~~~~~~~~
password.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int p=j;p<b.size();p++)
      |                     ~^~~~~~~~~
password.cpp:47:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if(nr==aux.size())
      |            ~~^~~~~~~~~~~~
password.cpp:58:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     while(i<a.size())
      |           ~^~~~~~~~~
password.cpp:63:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     while(j<b.size())
      |           ~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Guessed the password with 49 queries.
2 Correct 5 ms 208 KB Guessed the password with 117 queries.
3 Correct 1 ms 208 KB Guessed the password with 92 queries.
4 Correct 2 ms 308 KB Guessed the password with 216 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 328 KB Guessed the password with 4512 queries.
2 Correct 100 ms 336 KB Guessed the password with 10191 queries.
3 Correct 138 ms 312 KB Guessed the password with 12505 queries.
4 Correct 190 ms 348 KB Guessed the password with 20412 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 75 queries.
2 Correct 2 ms 208 KB Guessed the password with 185 queries.
3 Correct 3 ms 208 KB Guessed the password with 49 queries.
4 Correct 5 ms 208 KB Guessed the password with 117 queries.
5 Correct 1 ms 208 KB Guessed the password with 92 queries.
6 Correct 2 ms 308 KB Guessed the password with 216 queries.
7 Correct 42 ms 328 KB Guessed the password with 4512 queries.
8 Correct 100 ms 336 KB Guessed the password with 10191 queries.
9 Correct 138 ms 312 KB Guessed the password with 12505 queries.
10 Correct 190 ms 348 KB Guessed the password with 20412 queries.
11 Correct 378 ms 340 KB Guessed the password with 49508 queries.
12 Correct 117 ms 432 KB Guessed the password with 11387 queries.
13 Correct 450 ms 360 KB Guessed the password with 47682 queries.
14 Correct 205 ms 444 KB Guessed the password with 21356 queries.
15 Correct 404 ms 468 KB Guessed the password with 44836 queries.
16 Correct 113 ms 476 KB Guessed the password with 17935 queries.
17 Correct 407 ms 584 KB Guessed the password with 49794 queries.
18 Correct 156 ms 364 KB Guessed the password with 14832 queries.
19 Incorrect 440 ms 604 KB Could not guess the password with 50000 queries.
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 75 queries.
2 Correct 2 ms 208 KB Guessed the password with 185 queries.
3 Correct 3 ms 208 KB Guessed the password with 49 queries.
4 Correct 5 ms 208 KB Guessed the password with 117 queries.
5 Correct 1 ms 208 KB Guessed the password with 92 queries.
6 Correct 2 ms 308 KB Guessed the password with 216 queries.
7 Correct 42 ms 328 KB Guessed the password with 4512 queries.
8 Correct 100 ms 336 KB Guessed the password with 10191 queries.
9 Correct 138 ms 312 KB Guessed the password with 12505 queries.
10 Correct 190 ms 348 KB Guessed the password with 20412 queries.
11 Correct 378 ms 340 KB Guessed the password with 49508 queries.
12 Correct 117 ms 432 KB Guessed the password with 11387 queries.
13 Correct 450 ms 360 KB Guessed the password with 47682 queries.
14 Correct 205 ms 444 KB Guessed the password with 21356 queries.
15 Correct 404 ms 468 KB Guessed the password with 44836 queries.
16 Correct 113 ms 476 KB Guessed the password with 17935 queries.
17 Correct 407 ms 584 KB Guessed the password with 49794 queries.
18 Correct 156 ms 364 KB Guessed the password with 14832 queries.
19 Incorrect 440 ms 604 KB Could not guess the password with 50000 queries.
20 Halted 0 ms 0 KB -