oj.uz

답안 #476243

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476243 2021-09-25T14:49:22 Z iulia13 Password (RMI18_password) C++14
10 / 100
 100 ms 420 KB 
#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 + a[la];
        for (int i = lb; i < nb; i++)
            mystr += b[i];
        if (query(mystr) > cur)
        {
            cur = query(mystr);
            ans += a[la++];
        }
        else
            ans += b[lb++];
    }
    for (int i = lb; i < nb; i++)
        ans += b[i];
    for (int i = la; i < na; i++)
        ans += a[i];
    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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Guessed the password with 86 queries.
2 Correct 2 ms 200 KB Guessed the password with 141 queries.

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Guessed the password with 69 queries.
2 Correct 3 ms 200 KB Guessed the password with 208 queries.
3 Correct 2 ms 200 KB Guessed the password with 102 queries.
4 Runtime error 3 ms 200 KB Execution killed with signal 13

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 324 KB Guessed the password with 4960 queries.
2 Correct 76 ms 420 KB Guessed the password with 7665 queries.
3 Runtime error 100 ms 300 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Guessed the password with 86 queries.
2 Correct 2 ms 200 KB Guessed the password with 141 queries.
3 Correct 1 ms 200 KB Guessed the password with 69 queries.
4 Correct 3 ms 200 KB Guessed the password with 208 queries.
5 Correct 2 ms 200 KB Guessed the password with 102 queries.
6 Runtime error 3 ms 200 KB Execution killed with signal 13

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Guessed the password with 86 queries.
2 Correct 2 ms 200 KB Guessed the password with 141 queries.
3 Correct 1 ms 200 KB Guessed the password with 69 queries.
4 Correct 3 ms 200 KB Guessed the password with 208 queries.
5 Correct 2 ms 200 KB Guessed the password with 102 queries.
6 Runtime error 3 ms 200 KB Execution killed with signal 13