oj.uz

Submission #493888

# Submission time Handle Problem Language Result Execution time Memory
493888 2021-12-13T09:55:04 Z dekanycsaba Password (RMI18_password) C++14
30 / 100
 97 ms 660 KB 
#include <iostream>
#include <bits/stdc++.h>
#include<string>
#include<set>
#include<iterator>

using namespace std;

int s1, s2;
string p1, p2;
string megold="a";
int db=0;
int query(string str);

struct szov
{
    string ir;
    int hosz=0;

};

struct rendez{

bool operator()(szov const& a, szov const& b)
{
    return a.hosz<b.hosz;
}

};

multiset<szov,rendez> ms1;
multiset<szov,rendez>::iterator itr;

szov proba;

string merging(string f1, string f2)
{
    string a3;
    string e1,e2;
    string ossz;
   while(f1.size()!=0 || f2.size()!=0)
    {
        if(f1.size()==0)
        {
            a3=a3+f2;
            f2.clear();
        }
        else if(f2.size()==0)
        {
            a3=a3+f1;
            f1.clear();
        }
        else{
            e1=f1[0];
            e2=f2[0];
            ossz=a3+e1+f2;
            s2=query(ossz);
            db++;
            if(s2==ossz.size())
            {
                a3=a3+e1;
                f1.erase(f1.begin());
            }
            else{
                a3=a3+e2;
                f2.erase(f2.begin());
            }
        }
    }

    return a3;
}

string guess(int N, int S)
{
    string help="aabcdefghijklmnopqrstuvwxyz";
    string T[27]={};
    for(int j=1;j<N+1;j++)
    {
        for(int i=1;i<S+1;i++)
    {
        T[i]=T[i]+help[i];
    }
    }
    for(int i=1;i<S+1;i++)
    {
        s1=query(T[i]);
        if(s1>0)
        {
            proba.hosz=s1;
            proba.ir.clear();
            for(int j=1;j<s1+1;j++)
            {
                proba.ir=proba.ir+help[i];
            }
            ms1.insert(proba);
        }
    }
    while(ms1.size()>1 && db<25000)
    {
        itr=ms1.begin();
        p1=(*itr).ir;
        ms1.erase(itr);
        itr=ms1.begin();
        p2=(*itr).ir;
        ms1.erase(itr);
        proba.hosz=p1.size()+p2.size();
        proba.ir=merging(p1,p2);
        ms1.insert(proba);
    }
    if(ms1.size()==1)
    {
         itr=ms1.begin();
         megold=(*itr).ir;
    }

return megold;
}

Compilation message

password.cpp: In function 'std::string merging(std::string, std::string)':
password.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             if(s2==ossz.size())
      |                ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 58 queries.
2 Correct 2 ms 200 KB Guessed the password with 103 queries.

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 49 queries.
2 Runtime error 1 ms 200 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 564 KB Guessed the password with 2750 queries.
2 Correct 46 ms 584 KB Guessed the password with 5070 queries.
3 Correct 79 ms 584 KB Guessed the password with 4588 queries.
4 Correct 97 ms 660 KB Guessed the password with 8085 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 58 queries.
2 Correct 2 ms 200 KB Guessed the password with 103 queries.
3 Correct 1 ms 200 KB Guessed the password with 49 queries.
4 Runtime error 1 ms 200 KB Execution killed with signal 13
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 58 queries.
2 Correct 2 ms 200 KB Guessed the password with 103 queries.
3 Correct 1 ms 200 KB Guessed the password with 49 queries.
4 Runtime error 1 ms 200 KB Execution killed with signal 13
5 Halted 0 ms 0 KB -