oj.uz

Submission #1093737

# Submission time Handle Problem Language Result Execution time Memory
1093737 2024-09-27T10:56:17 Z DobromirAngelov Password (RMI18_password) C++14
50 / 100
 65 ms 728 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({-seq[i].size(), i});
    }

    while(pq.size()>1)
    {
        int ind1=pq.top().second;
        pq.pop();
        int ind2=pq.top().second;
        pq.pop();
        pq.push({-seq[ind1].size()-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 1 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 476 KB Guessed the password with 2758 queries.
2 Correct 31 ms 684 KB Guessed the password with 5097 queries.
3 Correct 37 ms 728 KB Guessed the password with 4590 queries.
4 Correct 49 ms 692 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 1 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 476 KB Guessed the password with 2758 queries.
8 Correct 31 ms 684 KB Guessed the password with 5097 queries.
9 Correct 37 ms 728 KB Guessed the password with 4590 queries.
10 Correct 49 ms 692 KB Guessed the password with 8142 queries.
11 Correct 65 ms 704 KB Guessed the password with 8162 queries.
12 Runtime error 60 ms 504 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 1 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 476 KB Guessed the password with 2758 queries.
8 Correct 31 ms 684 KB Guessed the password with 5097 queries.
9 Correct 37 ms 728 KB Guessed the password with 4590 queries.
10 Correct 49 ms 692 KB Guessed the password with 8142 queries.
11 Correct 65 ms 704 KB Guessed the password with 8162 queries.
12 Runtime error 60 ms 504 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -