oj.uz

Submission #791671

# Submission time Handle Problem Language Result Execution time Memory
791671 2023-07-24T08:44:04 Z anton Password (RMI18_password) C++17
100 / 100
 196 ms 588 KB 
#include <bits/stdc++.h>

using namespace std;

int query(string q);

string uni(char c, int l){
  string r;
  for(int i = 0; i<l; i++){
    r.push_back(c);
  }
  return r;
}

string merge(string a, string b){
  if(a.size()<b.size()){
    return merge(b, a);
  }

  int p = 0;
  int nb_ins= 0;
  while(p<=a.size()&& nb_ins<b.size()){
    string r2 = a;
    r2.insert(r2.begin()+ p, b[nb_ins]);
    if(query(r2) == r2.size()){
      swap(a, r2);
      nb_ins++;
    }
    p++;
  }

  return a;
}

vector<int> oc;
string dpr(int lt, int rt){
  if(lt == rt){
    return uni(lt+'a', oc[lt]);
  }
  else{
    int mid = (lt+rt)/2;

    return merge(dpr(lt, mid), dpr(mid+1, rt));
  }
}


string guess(int n, int s){
  string r;
  oc.resize(s);
  for(int i = 0; i<s; i++){
    string a;
    int l =0;
    char c= 'a'+i;


    oc[i] = query(uni(c, n));
    //cout<<c<<" "<<oc[i]<<endl;
  }

  r = dpr(0, s-1);

  return r;
}

Compilation message

password.cpp: In function 'std::string merge(std::string, std::string)':
password.cpp:22:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   while(p<=a.size()&& nb_ins<b.size()){
      |         ~^~~~~~~~~~
password.cpp:22:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   while(p<=a.size()&& nb_ins<b.size()){
      |                       ~~~~~~^~~~~~~~~
password.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     if(query(r2) == r2.size()){
      |        ~~~~~~~~~~^~~~~~~~~~~~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:53:9: warning: unused variable 'l' [-Wunused-variable]
   53 |     int l =0;
      |         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 68 queries.
2 Correct 1 ms 208 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 52 queries.
2 Correct 1 ms 208 KB Guessed the password with 116 queries.
3 Correct 1 ms 208 KB Guessed the password with 105 queries.
4 Correct 2 ms 300 KB Guessed the password with 199 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 324 KB Guessed the password with 3462 queries.
2 Correct 26 ms 588 KB Guessed the password with 5035 queries.
3 Correct 35 ms 340 KB Guessed the password with 6355 queries.
4 Correct 44 ms 484 KB Guessed the password with 8715 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 68 queries.
2 Correct 1 ms 208 KB Guessed the password with 111 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 1 ms 208 KB Guessed the password with 116 queries.
5 Correct 1 ms 208 KB Guessed the password with 105 queries.
6 Correct 2 ms 300 KB Guessed the password with 199 queries.
7 Correct 30 ms 324 KB Guessed the password with 3462 queries.
8 Correct 26 ms 588 KB Guessed the password with 5035 queries.
9 Correct 35 ms 340 KB Guessed the password with 6355 queries.
10 Correct 44 ms 484 KB Guessed the password with 8715 queries.
11 Correct 111 ms 432 KB Guessed the password with 13650 queries.
12 Correct 105 ms 356 KB Guessed the password with 12460 queries.
13 Correct 104 ms 468 KB Guessed the password with 14407 queries.
14 Correct 119 ms 376 KB Guessed the password with 13973 queries.
15 Correct 127 ms 360 KB Guessed the password with 15077 queries.
16 Correct 135 ms 356 KB Guessed the password with 14160 queries.
17 Correct 95 ms 472 KB Guessed the password with 16061 queries.
18 Correct 117 ms 336 KB Guessed the password with 15212 queries.
19 Correct 136 ms 472 KB Guessed the password with 16417 queries.
20 Correct 125 ms 344 KB Guessed the password with 14253 queries.
21 Correct 162 ms 372 KB Guessed the password with 16875 queries.
22 Correct 134 ms 440 KB Guessed the password with 15478 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 68 queries.
2 Correct 1 ms 208 KB Guessed the password with 111 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 1 ms 208 KB Guessed the password with 116 queries.
5 Correct 1 ms 208 KB Guessed the password with 105 queries.
6 Correct 2 ms 300 KB Guessed the password with 199 queries.
7 Correct 30 ms 324 KB Guessed the password with 3462 queries.
8 Correct 26 ms 588 KB Guessed the password with 5035 queries.
9 Correct 35 ms 340 KB Guessed the password with 6355 queries.
10 Correct 44 ms 484 KB Guessed the password with 8715 queries.
11 Correct 111 ms 432 KB Guessed the password with 13650 queries.
12 Correct 105 ms 356 KB Guessed the password with 12460 queries.
13 Correct 104 ms 468 KB Guessed the password with 14407 queries.
14 Correct 119 ms 376 KB Guessed the password with 13973 queries.
15 Correct 127 ms 360 KB Guessed the password with 15077 queries.
16 Correct 135 ms 356 KB Guessed the password with 14160 queries.
17 Correct 95 ms 472 KB Guessed the password with 16061 queries.
18 Correct 117 ms 336 KB Guessed the password with 15212 queries.
19 Correct 136 ms 472 KB Guessed the password with 16417 queries.
20 Correct 125 ms 344 KB Guessed the password with 14253 queries.
21 Correct 162 ms 372 KB Guessed the password with 16875 queries.
22 Correct 134 ms 440 KB Guessed the password with 15478 queries.
23 Correct 169 ms 516 KB Guessed the password with 23705 queries.
24 Correct 159 ms 492 KB Guessed the password with 22240 queries.
25 Correct 196 ms 392 KB Guessed the password with 23865 queries.
26 Correct 192 ms 484 KB Guessed the password with 23349 queries.
27 Correct 175 ms 476 KB Guessed the password with 23792 queries.
28 Correct 194 ms 472 KB Guessed the password with 23049 queries.
29 Correct 191 ms 400 KB Guessed the password with 23871 queries.
30 Correct 174 ms 348 KB Guessed the password with 22509 queries.