oj.uz

Submission #493894

# Submission time Handle Problem Language Result Execution time Memory
493894 2021-12-13T09:59:07 Z dekanycsaba Password (RMI18_password) C++14
100 / 100
 302 ms 1124 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<20000)
    {
        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 2 ms 200 KB Guessed the password with 58 queries.
2 Correct 1 ms 200 KB Guessed the password with 103 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 49 queries.
2 Correct 2 ms 200 KB Guessed the password with 90 queries.
3 Correct 1 ms 200 KB Guessed the password with 92 queries.
4 Correct 3 ms 200 KB Guessed the password with 178 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 584 KB Guessed the password with 2750 queries.
2 Correct 44 ms 704 KB Guessed the password with 5070 queries.
3 Correct 40 ms 604 KB Guessed the password with 4588 queries.
4 Correct 103 ms 656 KB Guessed the password with 8085 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 58 queries.
2 Correct 1 ms 200 KB Guessed the password with 103 queries.
3 Correct 2 ms 200 KB Guessed the password with 49 queries.
4 Correct 2 ms 200 KB Guessed the password with 90 queries.
5 Correct 1 ms 200 KB Guessed the password with 92 queries.
6 Correct 3 ms 200 KB Guessed the password with 178 queries.
7 Correct 33 ms 584 KB Guessed the password with 2750 queries.
8 Correct 44 ms 704 KB Guessed the password with 5070 queries.
9 Correct 40 ms 604 KB Guessed the password with 4588 queries.
10 Correct 103 ms 656 KB Guessed the password with 8085 queries.
11 Correct 126 ms 756 KB Guessed the password with 8156 queries.
12 Correct 80 ms 748 KB Guessed the password with 8162 queries.
13 Correct 132 ms 712 KB Guessed the password with 11502 queries.
14 Correct 96 ms 716 KB Guessed the password with 11602 queries.
15 Correct 159 ms 832 KB Guessed the password with 10880 queries.
16 Correct 129 ms 776 KB Guessed the password with 10861 queries.
17 Correct 134 ms 776 KB Guessed the password with 10212 queries.
18 Correct 129 ms 776 KB Guessed the password with 10245 queries.
19 Correct 89 ms 800 KB Guessed the password with 9686 queries.
20 Correct 75 ms 712 KB Guessed the password with 9775 queries.
21 Correct 124 ms 788 KB Guessed the password with 11644 queries.
22 Correct 112 ms 788 KB Guessed the password with 11712 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 58 queries.
2 Correct 1 ms 200 KB Guessed the password with 103 queries.
3 Correct 2 ms 200 KB Guessed the password with 49 queries.
4 Correct 2 ms 200 KB Guessed the password with 90 queries.
5 Correct 1 ms 200 KB Guessed the password with 92 queries.
6 Correct 3 ms 200 KB Guessed the password with 178 queries.
7 Correct 33 ms 584 KB Guessed the password with 2750 queries.
8 Correct 44 ms 704 KB Guessed the password with 5070 queries.
9 Correct 40 ms 604 KB Guessed the password with 4588 queries.
10 Correct 103 ms 656 KB Guessed the password with 8085 queries.
11 Correct 126 ms 756 KB Guessed the password with 8156 queries.
12 Correct 80 ms 748 KB Guessed the password with 8162 queries.
13 Correct 132 ms 712 KB Guessed the password with 11502 queries.
14 Correct 96 ms 716 KB Guessed the password with 11602 queries.
15 Correct 159 ms 832 KB Guessed the password with 10880 queries.
16 Correct 129 ms 776 KB Guessed the password with 10861 queries.
17 Correct 134 ms 776 KB Guessed the password with 10212 queries.
18 Correct 129 ms 776 KB Guessed the password with 10245 queries.
19 Correct 89 ms 800 KB Guessed the password with 9686 queries.
20 Correct 75 ms 712 KB Guessed the password with 9775 queries.
21 Correct 124 ms 788 KB Guessed the password with 11644 queries.
22 Correct 112 ms 788 KB Guessed the password with 11712 queries.
23 Correct 250 ms 940 KB Guessed the password with 23704 queries.
24 Correct 236 ms 1100 KB Guessed the password with 20965 queries.
25 Correct 302 ms 896 KB Guessed the password with 23669 queries.
26 Correct 226 ms 1000 KB Guessed the password with 19099 queries.
27 Correct 277 ms 988 KB Guessed the password with 23703 queries.
28 Correct 239 ms 892 KB Guessed the password with 16823 queries.
29 Correct 279 ms 1124 KB Guessed the password with 23707 queries.
30 Correct 225 ms 1108 KB Guessed the password with 14390 queries.