oj.uz

Submission #641171

# Submission time Handle Problem Language Result Execution time Memory
641171 2022-09-16T06:49:31 Z Tenis0206 Password (RMI18_password) C++14
50 / 100
 449 ms 456 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 88 queries.
2 Correct 2 ms 208 KB Guessed the password with 182 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 129 queries.
3 Correct 2 ms 208 KB Guessed the password with 169 queries.
4 Correct 3 ms 208 KB Guessed the password with 264 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 336 KB Guessed the password with 8258 queries.
2 Correct 83 ms 456 KB Guessed the password with 10632 queries.
3 Correct 164 ms 348 KB Guessed the password with 19409 queries.
4 Correct 228 ms 356 KB Guessed the password with 26458 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 88 queries.
2 Correct 2 ms 208 KB Guessed the password with 182 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 129 queries.
5 Correct 2 ms 208 KB Guessed the password with 169 queries.
6 Correct 3 ms 208 KB Guessed the password with 264 queries.
7 Correct 67 ms 336 KB Guessed the password with 8258 queries.
8 Correct 83 ms 456 KB Guessed the password with 10632 queries.
9 Correct 164 ms 348 KB Guessed the password with 19409 queries.
10 Correct 228 ms 356 KB Guessed the password with 26458 queries.
11 Incorrect 449 ms 360 KB Could not guess the password with 50000 queries.
12 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 88 queries.
2 Correct 2 ms 208 KB Guessed the password with 182 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 129 queries.
5 Correct 2 ms 208 KB Guessed the password with 169 queries.
6 Correct 3 ms 208 KB Guessed the password with 264 queries.
7 Correct 67 ms 336 KB Guessed the password with 8258 queries.
8 Correct 83 ms 456 KB Guessed the password with 10632 queries.
9 Correct 164 ms 348 KB Guessed the password with 19409 queries.
10 Correct 228 ms 356 KB Guessed the password with 26458 queries.
11 Incorrect 449 ms 360 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -