답안 #1093745

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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++)
      |                 ~^~~~~~~~~~~
# 결과 실행 시간 메모리 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.
# 결과 실행 시간 메모리 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.
# 결과 실행 시간 메모리 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.
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -