Submission #520400

#	Time	Username	Problem	Language	Result	Execution time	Memory
520400		Alex_tz307	Password (RMI18_password)	C++17	100 / 100	263 ms	704 KiB

password

#include <bits/stdc++.h>

using namespace std;

struct sir {
  string s;

  sir() : s("") {}

  bool operator < (const sir &a) const {
    return s.size() > a.s.size();
  };
};

int query(string);

string guess(int n, int m) {
  priority_queue<sir> pq;
  int sum_freq = 0;
  for (int i = 0; i <= m - 1; ++i) {
    char c = i + 97;
    int freq;
    if (i <= m - 2) {
      string aux = "";
      for (int j = 0; j <= n - 1; ++j) {
        aux += c;
      }
      freq = query(aux);
      sum_freq += freq;
    } else {
      freq = n - sum_freq;
    }
    sir a;
    for (int j = 0; j <= freq - 1; ++j) {
      a.s += c;
    }
    pq.push(a);
  }
  while ((int)pq.size() >= 2) {
    sir a = pq.top();
    pq.pop();
    sir b = pq.top();
    pq.pop();
    sir c;
    while (a.s.empty() == false && b.s.empty() == false) {
      string aux = "";
      aux += c.s;
      aux += a.s[0];
      aux += b.s;
      if (query(aux) == 1 + c.s.size() + b.s.size()) {
        c.s += a.s[0];
        a.s.erase(a.s.begin());
      } else {
        c.s += b.s[0];
        b.s.erase(b.s.begin());
      }
    }
    c.s += a.s;
    c.s += b.s;
    pq.push(c);
  }
  return pq.top().s;
}

Compilation message (stderr)

password.cpp: In function 'std::string guess(int, int)':
password.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |       if (query(aux) == 1 + c.s.size() + b.s.size()) {
      |           ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20