oj.uz

Submission #288089

# Submission time Handle Problem Language Result Execution time Memory
288089 2020-09-01T08:39:32 Z achibasadzishvili Password (RMI18_password) C++14
100 / 100
 362 ms 668 KB 
#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
string s;
int query(string str);
string guess(int n,int s){
    ll raod[40];
    for(int i=0; i<30; i++)raod[i] = 0;
    vector<string>v;
    for(int i=0; i<s; i++){
        char c = char('a' + i);
        string k;
        for(int j=0; j<n; j++)k += c;
        raod[i] = query(k);
        k = "";
        for(int j=0; j<raod[i]; j++)k += c;
        if(k.size())v.pb(k);
    }
    string ne;
    ll t;
    while(v.size() > 1){
        vector<string>v1;
        for(int i0=0; i0<(int)v.size()-1; i0+=2){
            int i1 = i0 + 1;
            ll l = 0,r = 0;
            string cur = "";
            while(l < v[i0].size() && r < v[i1].size()){
                ne = cur;
                ne += v[i0][l];
                for(int i=r; i<v[i1].size(); i++)ne += v[i1][i];
                t = query(ne);
                if(t == l + 1 + v[i1].size()){
                    cur += v[i0][l];
                    l++;
                }
                else {
                    cur += v[i1][r];
                    r++;
                }
            }
            while(l < v[i0].size()){
                cur += v[i0][l];
                l++;
            }
            while(r < v[i1].size()){
                cur += v[i1][r];
                r++;
            }
            v1.pb(cur);
        }
        if(v.size()%2==1)v1.pb(v.back());
        v = v1;
    }
    return v[0];
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             while(l < v[i0].size() && r < v[i1].size()){
      |                   ~~^~~~~~~~~~~~~~
password.cpp:30:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             while(l < v[i0].size() && r < v[i1].size()){
      |                                       ~~^~~~~~~~~~~~~~
password.cpp:33:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                 for(int i=r; i<v[i1].size(); i++)ne += v[i1][i];
      |                              ~^~~~~~~~~~~~~
password.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |                 if(t == l + 1 + v[i1].size()){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~
password.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             while(l < v[i0].size()){
      |                   ~~^~~~~~~~~~~~~~
password.cpp:48:21: 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(r < v[i1].size()){
      |                   ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 256 KB Guessed the password with 3473 queries.
2 Correct 62 ms 256 KB Guessed the password with 5025 queries.
3 Correct 95 ms 376 KB Guessed the password with 6858 queries.
4 Correct 151 ms 384 KB Guessed the password with 9073 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 61 queries.
2 Correct 2 ms 256 KB Guessed the password with 103 queries.
3 Correct 2 ms 256 KB Guessed the password with 49 queries.
4 Correct 2 ms 256 KB Guessed the password with 117 queries.
5 Correct 1 ms 256 KB Guessed the password with 92 queries.
6 Correct 2 ms 288 KB Guessed the password with 197 queries.
7 Correct 43 ms 256 KB Guessed the password with 3473 queries.
8 Correct 62 ms 256 KB Guessed the password with 5025 queries.
9 Correct 95 ms 376 KB Guessed the password with 6858 queries.
10 Correct 151 ms 384 KB Guessed the password with 9073 queries.
11 Correct 149 ms 384 KB Guessed the password with 13608 queries.
12 Correct 189 ms 384 KB Guessed the password with 11100 queries.
13 Correct 186 ms 388 KB Guessed the password with 14701 queries.
14 Correct 178 ms 384 KB Guessed the password with 13487 queries.
15 Correct 194 ms 512 KB Guessed the password with 14843 queries.
16 Correct 197 ms 380 KB Guessed the password with 13540 queries.
17 Correct 190 ms 384 KB Guessed the password with 16238 queries.
18 Correct 201 ms 400 KB Guessed the password with 13756 queries.
19 Correct 229 ms 384 KB Guessed the password with 16676 queries.
20 Correct 195 ms 384 KB Guessed the password with 12434 queries.
21 Correct 220 ms 504 KB Guessed the password with 17141 queries.
22 Correct 191 ms 508 KB Guessed the password with 14499 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 61 queries.
2 Correct 2 ms 256 KB Guessed the password with 103 queries.
3 Correct 2 ms 256 KB Guessed the password with 49 queries.
4 Correct 2 ms 256 KB Guessed the password with 117 queries.
5 Correct 1 ms 256 KB Guessed the password with 92 queries.
6 Correct 2 ms 288 KB Guessed the password with 197 queries.
7 Correct 43 ms 256 KB Guessed the password with 3473 queries.
8 Correct 62 ms 256 KB Guessed the password with 5025 queries.
9 Correct 95 ms 376 KB Guessed the password with 6858 queries.
10 Correct 151 ms 384 KB Guessed the password with 9073 queries.
11 Correct 149 ms 384 KB Guessed the password with 13608 queries.
12 Correct 189 ms 384 KB Guessed the password with 11100 queries.
13 Correct 186 ms 388 KB Guessed the password with 14701 queries.
14 Correct 178 ms 384 KB Guessed the password with 13487 queries.
15 Correct 194 ms 512 KB Guessed the password with 14843 queries.
16 Correct 197 ms 380 KB Guessed the password with 13540 queries.
17 Correct 190 ms 384 KB Guessed the password with 16238 queries.
18 Correct 201 ms 400 KB Guessed the password with 13756 queries.
19 Correct 229 ms 384 KB Guessed the password with 16676 queries.
20 Correct 195 ms 384 KB Guessed the password with 12434 queries.
21 Correct 220 ms 504 KB Guessed the password with 17141 queries.
22 Correct 191 ms 508 KB Guessed the password with 14499 queries.
23 Correct 362 ms 416 KB Guessed the password with 24023 queries.
24 Correct 287 ms 432 KB Guessed the password with 22706 queries.
25 Correct 313 ms 412 KB Guessed the password with 24096 queries.
26 Correct 352 ms 612 KB Guessed the password with 24566 queries.
27 Correct 303 ms 668 KB Guessed the password with 24136 queries.
28 Correct 275 ms 416 KB Guessed the password with 23569 queries.
29 Correct 321 ms 592 KB Guessed the password with 24179 queries.
30 Correct 315 ms 516 KB Guessed the password with 22392 queries.