oj.uz

Submission #1093746

# Submission time Handle Problem Language Result Execution time Memory
1093746 2024-09-27T11:02:35 Z DobromirAngelov Password (RMI18_password) C++14
50 / 100
 73 ms 872 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=(int)seq[ind2].size()-1;
    for(int i=(int)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+(int)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((int)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: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 596 KB Guessed the password with 48 queries.
2 Correct 0 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 15 ms 600 KB Guessed the password with 2758 queries.
2 Correct 30 ms 716 KB Guessed the password with 5097 queries.
3 Correct 33 ms 692 KB Guessed the password with 4590 queries.
4 Correct 65 ms 872 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 596 KB Guessed the password with 48 queries.
4 Correct 0 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 15 ms 600 KB Guessed the password with 2758 queries.
8 Correct 30 ms 716 KB Guessed the password with 5097 queries.
9 Correct 33 ms 692 KB Guessed the password with 4590 queries.
10 Correct 65 ms 872 KB Guessed the password with 8142 queries.
11 Correct 70 ms 724 KB Guessed the password with 8162 queries.
12 Runtime error 73 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 596 KB Guessed the password with 48 queries.
4 Correct 0 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 15 ms 600 KB Guessed the password with 2758 queries.
8 Correct 30 ms 716 KB Guessed the password with 5097 queries.
9 Correct 33 ms 692 KB Guessed the password with 4590 queries.
10 Correct 65 ms 872 KB Guessed the password with 8142 queries.
11 Correct 70 ms 724 KB Guessed the password with 8162 queries.
12 Runtime error 73 ms 500 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -