Submission #791671

#	Time	Username	Problem	Language	Result	Execution time	Memory
791671		anton	Password (RMI18_password)	C++17	100 / 100	196 ms	588 KiB

password

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20