oj.uz

Submission #1093745

# Submission time Handle Problem Language Result Execution time Memory
1093745 2024-09-27T11:00:35 Z DobromirAngelov Password (RMI18_password) C++14
50 / 100
 64 ms 992 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(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 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 20 ms 472 KB Guessed the password with 2758 queries.
2 Correct 32 ms 456 KB Guessed the password with 5097 queries.
3 Correct 36 ms 592 KB Guessed the password with 4590 queries.
4 Correct 56 ms 744 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 0 ms 344 KB Guessed the password with 18 queries.
6 Correct 1 ms 344 KB Guessed the password with 175 queries.
7 Correct 20 ms 472 KB Guessed the password with 2758 queries.
8 Correct 32 ms 456 KB Guessed the password with 5097 queries.
9 Correct 36 ms 592 KB Guessed the password with 4590 queries.
10 Correct 56 ms 744 KB Guessed the password with 8142 queries.
11 Correct 64 ms 992 KB Guessed the password with 8162 queries.
12 Runtime error 64 ms 984 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 0 ms 344 KB Guessed the password with 18 queries.
6 Correct 1 ms 344 KB Guessed the password with 175 queries.
7 Correct 20 ms 472 KB Guessed the password with 2758 queries.
8 Correct 32 ms 456 KB Guessed the password with 5097 queries.
9 Correct 36 ms 592 KB Guessed the password with 4590 queries.
10 Correct 56 ms 744 KB Guessed the password with 8142 queries.
11 Correct 64 ms 992 KB Guessed the password with 8162 queries.
12 Runtime error 64 ms 984 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -