oj.uz

Submission #1087904

# Submission time Handle Problem Language Result Execution time Memory
1087904 2024-09-13T11:34:17 Z ASN49K Password (RMI18_password) C++14
100 / 100
 187 ms 1204 KB 
#include <bits/stdc++.h>
using namespace std;
int query(string str);

//kind of a merge sort algorithm
//log2(26)*2*n+26 operations but it's much better in practice if the test are random or we randomize
string divide(int n,int l,int r)
{
    if(l==r)
    {
        //number of apperances of a char
        return string(query(string(n,char('a'+l))) , char('a'+l));
    }
    int m=(l+r)/2;
    string a=divide(n,l,m),b=divide(n,m+1,r),rez;
    while(a.size() && b.size())
    {
      	//the next postion of a char for the result is either from a or from b
      	//we verify if position(a[0])<position(b[0])
        if(query(rez+a[0]+b)==rez.size()+1+b.size())
        {
            rez.push_back(a[0]);
            a.erase(a.begin());
        }
        else
        {
            rez.push_back(b[0]);
            b.erase(b.begin());
        }
    }
  	//we add the remainings
    rez+=a;
    rez+=b;
    return rez;
}
string guess(int n, int s)
{
    return divide(n,0,s-1);
}

Compilation message

password.cpp: In function 'std::string divide(int, int, int)':
password.cpp:20:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         if(query(rez+a[0]+b)==rez.size()+1+b.size())
      |            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 61 queries.
2 Correct 1 ms 344 KB Guessed the password with 101 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 49 queries.
2 Correct 1 ms 344 KB Guessed the password with 117 queries.
3 Correct 1 ms 344 KB Guessed the password with 92 queries.
4 Correct 1 ms 344 KB Guessed the password with 197 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 452 KB Guessed the password with 3456 queries.
2 Correct 32 ms 592 KB Guessed the password with 5025 queries.
3 Correct 41 ms 600 KB Guessed the password with 6352 queries.
4 Correct 70 ms 704 KB Guessed the password with 8693 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 61 queries.
2 Correct 1 ms 344 KB Guessed the password with 101 queries.
3 Correct 1 ms 344 KB Guessed the password with 49 queries.
4 Correct 1 ms 344 KB Guessed the password with 117 queries.
5 Correct 1 ms 344 KB Guessed the password with 92 queries.
6 Correct 1 ms 344 KB Guessed the password with 197 queries.
7 Correct 18 ms 452 KB Guessed the password with 3456 queries.
8 Correct 32 ms 592 KB Guessed the password with 5025 queries.
9 Correct 41 ms 600 KB Guessed the password with 6352 queries.
10 Correct 70 ms 704 KB Guessed the password with 8693 queries.
11 Correct 109 ms 592 KB Guessed the password with 13638 queries.
12 Correct 93 ms 924 KB Guessed the password with 12459 queries.
13 Correct 110 ms 712 KB Guessed the password with 14392 queries.
14 Correct 108 ms 724 KB Guessed the password with 13937 queries.
15 Correct 110 ms 712 KB Guessed the password with 15073 queries.
16 Correct 88 ms 720 KB Guessed the password with 14154 queries.
17 Correct 101 ms 476 KB Guessed the password with 16054 queries.
18 Correct 108 ms 600 KB Guessed the password with 15189 queries.
19 Correct 128 ms 724 KB Guessed the password with 16410 queries.
20 Correct 119 ms 472 KB Guessed the password with 14247 queries.
21 Correct 127 ms 476 KB Guessed the password with 16849 queries.
22 Correct 119 ms 476 KB Guessed the password with 15315 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 61 queries.
2 Correct 1 ms 344 KB Guessed the password with 101 queries.
3 Correct 1 ms 344 KB Guessed the password with 49 queries.
4 Correct 1 ms 344 KB Guessed the password with 117 queries.
5 Correct 1 ms 344 KB Guessed the password with 92 queries.
6 Correct 1 ms 344 KB Guessed the password with 197 queries.
7 Correct 18 ms 452 KB Guessed the password with 3456 queries.
8 Correct 32 ms 592 KB Guessed the password with 5025 queries.
9 Correct 41 ms 600 KB Guessed the password with 6352 queries.
10 Correct 70 ms 704 KB Guessed the password with 8693 queries.
11 Correct 109 ms 592 KB Guessed the password with 13638 queries.
12 Correct 93 ms 924 KB Guessed the password with 12459 queries.
13 Correct 110 ms 712 KB Guessed the password with 14392 queries.
14 Correct 108 ms 724 KB Guessed the password with 13937 queries.
15 Correct 110 ms 712 KB Guessed the password with 15073 queries.
16 Correct 88 ms 720 KB Guessed the password with 14154 queries.
17 Correct 101 ms 476 KB Guessed the password with 16054 queries.
18 Correct 108 ms 600 KB Guessed the password with 15189 queries.
19 Correct 128 ms 724 KB Guessed the password with 16410 queries.
20 Correct 119 ms 472 KB Guessed the password with 14247 queries.
21 Correct 127 ms 476 KB Guessed the password with 16849 queries.
22 Correct 119 ms 476 KB Guessed the password with 15315 queries.
23 Correct 177 ms 844 KB Guessed the password with 23612 queries.
24 Correct 163 ms 1040 KB Guessed the password with 22226 queries.
25 Correct 171 ms 1008 KB Guessed the password with 23794 queries.
26 Correct 187 ms 1204 KB Guessed the password with 23332 queries.
27 Correct 173 ms 944 KB Guessed the password with 23763 queries.
28 Correct 168 ms 900 KB Guessed the password with 23045 queries.
29 Correct 165 ms 1168 KB Guessed the password with 23847 queries.
30 Correct 182 ms 1168 KB Guessed the password with 22506 queries.