제출 #476244

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
476244		iulia13	Password (RMI18_password)	C++14	100 / 100	324 ms	592 KiB

password

#include <bits/stdc++.h>

using namespace std;
const int N = 5005;
string ans, prov;
int cnt[N], nn, ss;
int query(string str);
string p, password;/*
int query(string q) {


  int len = q.size();

  int i = 0, j = 0, plen = password.size();
  while (i < plen && j < len) {
    while ((i < plen) && (password[i] != q[j])) {
      i++;
    }
    if (i < plen) {
      i++;
      j++;
    }
  }


  return j;
}*/
string join(string a, string b)
{
    int na = a.size(), nb = b.size(), cur = nb;
    string ans = "", aa = a, bb = b;
    int la = 0, lb = 0;
    while (la < na && lb < nb)
    {
        string mystr = ans + aa[0] + bb;
        if (query(mystr) > cur)
        {
            cur++;
            ans += aa[0];
            aa.erase(aa.begin());
            la++;
        }
        else
        {
            lb++;
            ans += bb[0];
            bb.erase(bb.begin());
        }
    }
    ans += aa; ans += bb;
    return ans;
}
string divide(int l, int r, int n)
{
    string mystr = "";
    if (l == r)
    {
        char a = l + 'a';
        for (int i = 0; i < n; i++)
            mystr += a;
        int x = query(mystr);
        mystr = "";
        for (int i = 0; i < x; i++)
            mystr += a;
        return mystr;
    }
    int mid = (l + r) / 2;
    return join(divide(l, mid, n), divide(mid + 1, r, n));
}
string guess(int n, int s)
{
    return divide(0, s - 1, n);
}/*
int main()
{
    freopen("x.in", "r", stdin);
    freopen("x.out", "w", stdout);
    int nn, ss;
    cin >> nn >> ss;
    cin >> password;
    cout << guess(nn, ss);
    return 0;
}*/

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