oj.uz

Submission #641172

# Submission time Handle Problem Language Result Execution time Memory
641172 2022-09-16T06:59:32 Z Tenis0206 Password (RMI18_password) C++14
100 / 100
 315 ms 692 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];

struct cmp
{
    bool operator()(int a, int b)
    {
        return s[a].size() > s[b].size();
    }
};

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;
}

priority_queue<int,vector<int>,cmp> h;

string guess(int n, int cr)
{
    int cnt = 0;
    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);
        ++cnt;
        for(int j=1; j<=nr; j++)
        {
            s[cnt].push_back(c);
        }
        if(s[cnt].size() > 0)
        {
            h.push(cnt);
        }
    }
    while(h.size() > 1)
    {
        int poz1 = h.top();
        h.pop();
        int poz2 = h.top();
        h.pop();
        s[poz1] = Merge(s[poz1],s[poz2]);
        h.push(poz1);
    }
    return s[h.top()];
}

#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:47:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     while(i<a.size() && j<b.size())
      |           ~^~~~~~~~~
password.cpp:47:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     while(i<a.size() && j<b.size())
      |                         ~^~~~~~~~~
password.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int p=j; p<b.size(); p++)
      |                      ~^~~~~~~~~
password.cpp:55:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if(nr==aux.size())
      |            ~~^~~~~~~~~~~~
password.cpp:66:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     while(i<a.size())
      |           ~^~~~~~~~~
password.cpp:71:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     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 57 queries.
2 Correct 2 ms 208 KB Guessed the password with 105 queries.

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 316 KB Guessed the password with 2750 queries.
2 Correct 48 ms 360 KB Guessed the password with 5071 queries.
3 Correct 39 ms 332 KB Guessed the password with 4587 queries.
4 Correct 85 ms 568 KB Guessed the password with 8084 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 2 ms 208 KB Guessed the password with 105 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 1 ms 208 KB Guessed the password with 92 queries.
6 Correct 2 ms 208 KB Guessed the password with 178 queries.
7 Correct 29 ms 316 KB Guessed the password with 2750 queries.
8 Correct 48 ms 360 KB Guessed the password with 5071 queries.
9 Correct 39 ms 332 KB Guessed the password with 4587 queries.
10 Correct 85 ms 568 KB Guessed the password with 8084 queries.
11 Correct 100 ms 372 KB Guessed the password with 8161 queries.
12 Correct 60 ms 320 KB Guessed the password with 8160 queries.
13 Correct 133 ms 608 KB Guessed the password with 11502 queries.
14 Correct 112 ms 496 KB Guessed the password with 11602 queries.
15 Correct 113 ms 572 KB Guessed the password with 10881 queries.
16 Correct 107 ms 468 KB Guessed the password with 10861 queries.
17 Correct 120 ms 496 KB Guessed the password with 10211 queries.
18 Correct 115 ms 368 KB Guessed the password with 10249 queries.
19 Correct 127 ms 352 KB Guessed the password with 9685 queries.
20 Correct 92 ms 472 KB Guessed the password with 9777 queries.
21 Correct 136 ms 468 KB Guessed the password with 11644 queries.
22 Correct 143 ms 452 KB Guessed the password with 11713 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 2 ms 208 KB Guessed the password with 105 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 1 ms 208 KB Guessed the password with 92 queries.
6 Correct 2 ms 208 KB Guessed the password with 178 queries.
7 Correct 29 ms 316 KB Guessed the password with 2750 queries.
8 Correct 48 ms 360 KB Guessed the password with 5071 queries.
9 Correct 39 ms 332 KB Guessed the password with 4587 queries.
10 Correct 85 ms 568 KB Guessed the password with 8084 queries.
11 Correct 100 ms 372 KB Guessed the password with 8161 queries.
12 Correct 60 ms 320 KB Guessed the password with 8160 queries.
13 Correct 133 ms 608 KB Guessed the password with 11502 queries.
14 Correct 112 ms 496 KB Guessed the password with 11602 queries.
15 Correct 113 ms 572 KB Guessed the password with 10881 queries.
16 Correct 107 ms 468 KB Guessed the password with 10861 queries.
17 Correct 120 ms 496 KB Guessed the password with 10211 queries.
18 Correct 115 ms 368 KB Guessed the password with 10249 queries.
19 Correct 127 ms 352 KB Guessed the password with 9685 queries.
20 Correct 92 ms 472 KB Guessed the password with 9777 queries.
21 Correct 136 ms 468 KB Guessed the password with 11644 queries.
22 Correct 143 ms 452 KB Guessed the password with 11713 queries.
23 Correct 249 ms 656 KB Guessed the password with 23648 queries.
24 Correct 283 ms 608 KB Guessed the password with 20965 queries.
25 Correct 315 ms 424 KB Guessed the password with 23669 queries.
26 Correct 263 ms 476 KB Guessed the password with 19098 queries.
27 Correct 301 ms 692 KB Guessed the password with 23721 queries.
28 Correct 240 ms 472 KB Guessed the password with 16823 queries.
29 Correct 292 ms 404 KB Guessed the password with 23707 queries.
30 Correct 191 ms 488 KB Guessed the password with 14393 queries.