oj.uz

Submission #1093850

# Submission time Handle Problem Language Result Execution time Memory
1093850 2024-09-27T16:43:34 Z DobromirAngelov Password (RMI18_password) C++14
100 / 100
 201 ms 1340 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
int query(string str);
 
vector<string> seq;
priority_queue<pair<int,int> > pq;

int mergeQuery(int ind1,int len,string last)
{
    string str=seq[ind1].substr(0,len);
    reverse(last.begin(), last.end());
    str+=last;
    return query(str);
}
 
void mergeSeq(int ind1,int ind2)
{
    string ret="";
    int ptr=(int)seq[ind2].size()-1;
    for(int i=(int)seq[ind1].size()-1;i>=0;i--)
    {
        while(1)
        {
            if(ptr<0) break;
            ret+=seq[ind2][ptr];
            int cnt=mergeQuery(ind1,i+1,ret);
            if(cnt!=(i+1+(int)ret.size()))
            {
                ret.pop_back();
                break;
            }
            else ptr--;
        }
        ret+=seq[ind1][i];
    }
    for(int i=ptr;i>=0;i--) ret+=seq[ind2][i];
    reverse(ret.begin(), ret.end());
    seq[ind1]=ret;
}
 
string guess(int n,int s)
{
    for(int i=0;i<s;i++)
    {
        string str=string(n,(char)(i+'a'));
        int cnt=query(str);
        if(cnt>0)
        {
            string cur=string(cnt,(char)(i+'a'));
            seq.push_back(cur);
        }
    }
 
    for(int i=0;i<seq.size();i++)
    {
        pq.push({-((int)seq[i].size()), i});
    }
 
    while(pq.size()>1)
    {
        int ind1=pq.top().second;
        pq.pop();
        int ind2=pq.top().second;
        pq.pop();
        pq.push({-((int)seq[ind1].size()+(int)seq[ind2].size()),ind1});
        mergeSeq(ind1,ind2);
    }
 
    int ind=pq.top().second;
    return seq[ind];
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:56:18: 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]
   56 |     for(int i=0;i<seq.size();i++)
      |                 ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 57 queries.
2 Correct 1 ms 344 KB Guessed the password with 105 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Guessed the password with 48 queries.
2 Correct 1 ms 344 KB Guessed the password with 92 queries.
3 Correct 0 ms 344 KB Guessed the password with 18 queries.
4 Correct 1 ms 344 KB Guessed the password with 175 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 712 KB Guessed the password with 2757 queries.
2 Correct 30 ms 628 KB Guessed the password with 5084 queries.
3 Correct 31 ms 672 KB Guessed the password with 4587 queries.
4 Correct 50 ms 760 KB Guessed the password with 8126 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 57 queries.
2 Correct 1 ms 344 KB Guessed the password with 105 queries.
3 Correct 0 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 92 queries.
5 Correct 0 ms 344 KB Guessed the password with 18 queries.
6 Correct 1 ms 344 KB Guessed the password with 175 queries.
7 Correct 17 ms 712 KB Guessed the password with 2757 queries.
8 Correct 30 ms 628 KB Guessed the password with 5084 queries.
9 Correct 31 ms 672 KB Guessed the password with 4587 queries.
10 Correct 50 ms 760 KB Guessed the password with 8126 queries.
11 Correct 58 ms 852 KB Guessed the password with 8157 queries.
12 Correct 65 ms 972 KB Guessed the password with 8164 queries.
13 Correct 88 ms 684 KB Guessed the password with 11514 queries.
14 Correct 86 ms 716 KB Guessed the password with 11656 queries.
15 Correct 79 ms 600 KB Guessed the password with 10875 queries.
16 Correct 83 ms 708 KB Guessed the password with 10853 queries.
17 Correct 81 ms 760 KB Guessed the password with 10218 queries.
18 Correct 75 ms 756 KB Guessed the password with 10246 queries.
19 Correct 77 ms 704 KB Guessed the password with 9688 queries.
20 Correct 86 ms 700 KB Guessed the password with 9783 queries.
21 Correct 94 ms 716 KB Guessed the password with 11723 queries.
22 Correct 97 ms 504 KB Guessed the password with 11779 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 57 queries.
2 Correct 1 ms 344 KB Guessed the password with 105 queries.
3 Correct 0 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 92 queries.
5 Correct 0 ms 344 KB Guessed the password with 18 queries.
6 Correct 1 ms 344 KB Guessed the password with 175 queries.
7 Correct 17 ms 712 KB Guessed the password with 2757 queries.
8 Correct 30 ms 628 KB Guessed the password with 5084 queries.
9 Correct 31 ms 672 KB Guessed the password with 4587 queries.
10 Correct 50 ms 760 KB Guessed the password with 8126 queries.
11 Correct 58 ms 852 KB Guessed the password with 8157 queries.
12 Correct 65 ms 972 KB Guessed the password with 8164 queries.
13 Correct 88 ms 684 KB Guessed the password with 11514 queries.
14 Correct 86 ms 716 KB Guessed the password with 11656 queries.
15 Correct 79 ms 600 KB Guessed the password with 10875 queries.
16 Correct 83 ms 708 KB Guessed the password with 10853 queries.
17 Correct 81 ms 760 KB Guessed the password with 10218 queries.
18 Correct 75 ms 756 KB Guessed the password with 10246 queries.
19 Correct 77 ms 704 KB Guessed the password with 9688 queries.
20 Correct 86 ms 700 KB Guessed the password with 9783 queries.
21 Correct 94 ms 716 KB Guessed the password with 11723 queries.
22 Correct 97 ms 504 KB Guessed the password with 11779 queries.
23 Correct 201 ms 752 KB Guessed the password with 23693 queries.
24 Correct 166 ms 1032 KB Guessed the password with 20943 queries.
25 Correct 191 ms 768 KB Guessed the password with 23694 queries.
26 Correct 149 ms 968 KB Guessed the password with 19105 queries.
27 Correct 193 ms 1016 KB Guessed the password with 23732 queries.
28 Correct 145 ms 772 KB Guessed the password with 16828 queries.
29 Correct 194 ms 964 KB Guessed the password with 23691 queries.
30 Correct 123 ms 1340 KB Guessed the password with 14393 queries.