Submission #653896

#	Time	Username	Problem	Language	Result	Execution time	Memory
653896		MasterTaster	Password (RMI18_password)	C++14	100 / 100	219 ms	848 KiB

password

#include <iostream>
#include <string>

#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define ll long long

using namespace std;

int cnt[30];

int query(string q);

bool check1(char c, int k)
{
    string pitaj="";
    for (int i=0; i<k; i++) pitaj+=c;
    return query(pitaj)==pitaj.size();
}
string napravi(char c, int k)
{
    string s="";
    for (int i=0; i<k; i++) s+=c;
    return s;
}

bool check2(string a, int i, string dodaj)
{
    string pitaj="";
    if (i!=0) pitaj=a.substr(0, i);
    pitaj+=dodaj;
    if ((a.size()-i)!=0) pitaj+=a.substr(i, a.size()-i);

    return query(pitaj)==pitaj.size();
}

string spoj(string a, string b)
{
    if (a.size()>b.size()) swap(a, b);

    int j=0;
    string ret="";
    for (int i=0; i<=a.size(); i++)
    {
        string dodajes="";
        while (j<b.size())
        {
            dodajes+=b[j];
            if(check2(a, i, dodajes))
            {
                ret+=b[j];
                j++;
            }
            else break;
        }
        if (i!=a.size()) ret+=a[i];
    }

    return ret;
}

string mergesort(int l, int r)
{
    if (l==r)
        return napravi((char)('a'+l), cnt[l]);
    int mid=l+(r-l)/2;
    string a, b;
    a=mergesort(l, mid);
    b=mergesort(mid+1, r);
    string ret=spoj(a, b);
    return ret;
}

string guess(int n, int m)
{
    for (int i=0; i<m; i++)
    {
        char c=(char)('a'+i);

        int l=1, r=n;
        while (l<=r)
        {
            int mid=l+(r-l)/2;
            if (check1(c, mid))
            {
                l=mid+1;
                cnt[i]=mid;
            }
            else
                r=mid-1;
        }
    }

    return mergesort(0, m-1);
}

Compilation message (stderr)

password.cpp: In function 'bool check1(char, int)':
password.cpp:20:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     return query(pitaj)==pitaj.size();
      |            ~~~~~~~~~~~~^~~~~~~~~~~~~~
password.cpp: In function 'bool check2(std::string, int, std::string)':
password.cpp:36:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     return query(pitaj)==pitaj.size();
      |            ~~~~~~~~~~~~^~~~~~~~~~~~~~
password.cpp: In function 'std::string spoj(std::string, std::string)':
password.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i=0; i<=a.size(); i++)
      |                   ~^~~~~~~~~~
password.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         while (j<b.size())
      |                ~^~~~~~~~~
password.cpp:58:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         if (i!=a.size()) ret+=a[i];
      |             ~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20