oj.uz

Submission #1093741

# Submission time Handle Problem Language Result Execution time Memory
1093741 2024-09-27T10:59:11 Z DobromirAngelov Password (RMI18_password) C++14
50 / 100
 59 ms 740 KB 
#include<bits/stdc++.h>

using namespace std;

int query(string str);

vector<string> seq;
priority_queue<pair<int,int> > pq;

int queryLetter(char c,int cnt)
{
    string str="";
    for(int i=0;i<cnt;i++) str+=c;
    return query(str);
}

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=seq[ind2].size()-1;
    for(int i=seq[ind1].size()-1;i>=0;i--)
    {
        if(ptr>=0) ret+=seq[ind2][ptr];
        while(1)
        {
            int cnt=mergeQuery(ind1,i+1,ret);
            if(cnt!=(i+1+ret.size()))
            {
                ret.pop_back();
                break;
            }
            else ptr--;
            if(ptr<0) break;
            ret+=seq[ind2][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++)
    {
        int cnt=queryLetter((char)(i+'a'), n);
        if(cnt>0)
        {
            string cur="";
            for(int j=0;j<cnt;j++) cur+=(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 'void mergeSeq(int, int)':
password.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             if(cnt!=(i+1+ret.size()))
      |                ~~~^~~~~~~~~~~~~~~~~~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:64: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]
   64 |     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 59 queries.
2 Correct 1 ms 344 KB Guessed the password with 106 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 1 ms 344 KB Guessed the password with 18 queries.
4 Correct 2 ms 344 KB Guessed the password with 175 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 592 KB Guessed the password with 2758 queries.
2 Correct 34 ms 596 KB Guessed the password with 5097 queries.
3 Correct 30 ms 716 KB Guessed the password with 4590 queries.
4 Correct 58 ms 740 KB Guessed the password with 8142 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 59 queries.
2 Correct 1 ms 344 KB Guessed the password with 106 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 1 ms 344 KB Guessed the password with 18 queries.
6 Correct 2 ms 344 KB Guessed the password with 175 queries.
7 Correct 21 ms 592 KB Guessed the password with 2758 queries.
8 Correct 34 ms 596 KB Guessed the password with 5097 queries.
9 Correct 30 ms 716 KB Guessed the password with 4590 queries.
10 Correct 58 ms 740 KB Guessed the password with 8142 queries.
11 Correct 59 ms 500 KB Guessed the password with 8162 queries.
12 Runtime error 55 ms 500 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 59 queries.
2 Correct 1 ms 344 KB Guessed the password with 106 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 1 ms 344 KB Guessed the password with 18 queries.
6 Correct 2 ms 344 KB Guessed the password with 175 queries.
7 Correct 21 ms 592 KB Guessed the password with 2758 queries.
8 Correct 34 ms 596 KB Guessed the password with 5097 queries.
9 Correct 30 ms 716 KB Guessed the password with 4590 queries.
10 Correct 58 ms 740 KB Guessed the password with 8142 queries.
11 Correct 59 ms 500 KB Guessed the password with 8162 queries.
12 Runtime error 55 ms 500 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -