oj.uz

Submission #475330

# Submission time Handle Problem Language Result Execution time Memory
475330 2021-09-21T20:53:24 Z ogibogi2004 Password (RMI18_password) C++14
100 / 100
 302 ms 672 KB 
#include<bits/stdc++.h>
using namespace std;
int query(string s);
string tmp;
int n1;
string solve(int l,int r)
{
    if(l==r)
    {
        string s="";
        for(int j=0;;j++)
        {
            s+=char('a'+l);
            if(query(s)!=s.size())
            {
                s.pop_back();
                return s;
            }
        }
    }
    int mid=(l+r)/2;
    string s1=solve(l,mid);
    string s2=solve(mid+1,r);
    int len1=s1.size(),len2=s2.size();
    tmp="";
    int j=0;
    for(int i=0;i<=s1.size();i++)
    {
        if(j<s2.size())
        {
            tmp=s1;
            //cout<<tmp<<endl;
            tmp.insert(tmp.begin()+i,s2[j]);
            if(query(tmp)==tmp.size())
            {
                s1=tmp;
                j++;
            }
        }
    }
    while(j<s2.size())s1+=s2[j++];
    //if(j<s2.size())assert(false);
    //if(s1.size()==n1)assert(false);
    if(s1.size()!=len1+len2)assert(false);
    //cout<<l<<" "<<r<<" "<<s1<<endl;
    return s1;
}
string guess(int n,int s)
{
    n1=n;
    string f=solve(0,s-1);
    //if(f.size()!=n)assert(false);
    return f;
}

Compilation message

password.cpp: In function 'std::string solve(int, int)':
password.cpp:14:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |             if(query(s)!=s.size())
      |                ~~~~~~~~^~~~~~~~~~
password.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0;i<=s1.size();i++)
      |                 ~^~~~~~~~~~~
password.cpp:29:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         if(j<s2.size())
      |            ~^~~~~~~~~~
password.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             if(query(tmp)==tmp.size())
      |                ~~~~~~~~~~^~~~~~~~~~~~
password.cpp:41:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while(j<s2.size())s1+=s2[j++];
      |           ~^~~~~~~~~~
password.cpp:44:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(s1.size()!=len1+len2)assert(false);
      |        ~~~~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 98 queries.
2 Correct 1 ms 200 KB Guessed the password with 186 queries.
3 Correct 3 ms 200 KB Guessed the password with 183 queries.
4 Correct 3 ms 200 KB Guessed the password with 303 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 416 KB Guessed the password with 4704 queries.
2 Correct 61 ms 292 KB Guessed the password with 6353 queries.
3 Correct 90 ms 412 KB Guessed the password with 8184 queries.
4 Correct 108 ms 592 KB Guessed the password with 10721 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 83 queries.
2 Correct 2 ms 200 KB Guessed the password with 134 queries.
3 Correct 1 ms 200 KB Guessed the password with 98 queries.
4 Correct 1 ms 200 KB Guessed the password with 186 queries.
5 Correct 3 ms 200 KB Guessed the password with 183 queries.
6 Correct 3 ms 200 KB Guessed the password with 303 queries.
7 Correct 48 ms 416 KB Guessed the password with 4704 queries.
8 Correct 61 ms 292 KB Guessed the password with 6353 queries.
9 Correct 90 ms 412 KB Guessed the password with 8184 queries.
10 Correct 108 ms 592 KB Guessed the password with 10721 queries.
11 Correct 148 ms 324 KB Guessed the password with 16482 queries.
12 Correct 172 ms 444 KB Guessed the password with 15454 queries.
13 Correct 199 ms 452 KB Guessed the password with 17410 queries.
14 Correct 162 ms 408 KB Guessed the password with 16979 queries.
15 Correct 161 ms 408 KB Guessed the password with 18514 queries.
16 Correct 162 ms 456 KB Guessed the password with 17685 queries.
17 Correct 195 ms 552 KB Guessed the password with 19414 queries.
18 Correct 204 ms 404 KB Guessed the password with 18594 queries.
19 Correct 228 ms 464 KB Guessed the password with 19885 queries.
20 Correct 193 ms 452 KB Guessed the password with 18488 queries.
21 Correct 227 ms 316 KB Guessed the password with 20490 queries.
22 Correct 182 ms 332 KB Guessed the password with 19408 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 83 queries.
2 Correct 2 ms 200 KB Guessed the password with 134 queries.
3 Correct 1 ms 200 KB Guessed the password with 98 queries.
4 Correct 1 ms 200 KB Guessed the password with 186 queries.
5 Correct 3 ms 200 KB Guessed the password with 183 queries.
6 Correct 3 ms 200 KB Guessed the password with 303 queries.
7 Correct 48 ms 416 KB Guessed the password with 4704 queries.
8 Correct 61 ms 292 KB Guessed the password with 6353 queries.
9 Correct 90 ms 412 KB Guessed the password with 8184 queries.
10 Correct 108 ms 592 KB Guessed the password with 10721 queries.
11 Correct 148 ms 324 KB Guessed the password with 16482 queries.
12 Correct 172 ms 444 KB Guessed the password with 15454 queries.
13 Correct 199 ms 452 KB Guessed the password with 17410 queries.
14 Correct 162 ms 408 KB Guessed the password with 16979 queries.
15 Correct 161 ms 408 KB Guessed the password with 18514 queries.
16 Correct 162 ms 456 KB Guessed the password with 17685 queries.
17 Correct 195 ms 552 KB Guessed the password with 19414 queries.
18 Correct 204 ms 404 KB Guessed the password with 18594 queries.
19 Correct 228 ms 464 KB Guessed the password with 19885 queries.
20 Correct 193 ms 452 KB Guessed the password with 18488 queries.
21 Correct 227 ms 316 KB Guessed the password with 20490 queries.
22 Correct 182 ms 332 KB Guessed the password with 19408 queries.
23 Correct 287 ms 412 KB Guessed the password with 28708 queries.
24 Correct 262 ms 512 KB Guessed the password with 27770 queries.
25 Correct 254 ms 508 KB Guessed the password with 28853 queries.
26 Correct 292 ms 456 KB Guessed the password with 28374 queries.
27 Correct 270 ms 484 KB Guessed the password with 28807 queries.
28 Correct 274 ms 672 KB Guessed the password with 28436 queries.
29 Correct 275 ms 608 KB Guessed the password with 28873 queries.
30 Correct 302 ms 568 KB Guessed the password with 28818 queries.