oj.uz

Submission #476244

# Submission time Handle Problem Language Result Execution time Memory
476244 2021-09-25T14:55:13 Z iulia13 Password (RMI18_password) C++14
100 / 100
 324 ms 592 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 + 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 61 queries.
2 Correct 2 ms 200 KB Guessed the password with 101 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 49 queries.
2 Correct 1 ms 200 KB Guessed the password with 117 queries.
3 Correct 1 ms 200 KB Guessed the password with 92 queries.
4 Correct 4 ms 200 KB Guessed the password with 197 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 432 KB Guessed the password with 3456 queries.
2 Correct 64 ms 320 KB Guessed the password with 5025 queries.
3 Correct 81 ms 464 KB Guessed the password with 6352 queries.
4 Correct 92 ms 344 KB Guessed the password with 8693 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 61 queries.
2 Correct 2 ms 200 KB Guessed the password with 101 queries.
3 Correct 1 ms 200 KB Guessed the password with 49 queries.
4 Correct 1 ms 200 KB Guessed the password with 117 queries.
5 Correct 1 ms 200 KB Guessed the password with 92 queries.
6 Correct 4 ms 200 KB Guessed the password with 197 queries.
7 Correct 43 ms 432 KB Guessed the password with 3456 queries.
8 Correct 64 ms 320 KB Guessed the password with 5025 queries.
9 Correct 81 ms 464 KB Guessed the password with 6352 queries.
10 Correct 92 ms 344 KB Guessed the password with 8693 queries.
11 Correct 140 ms 468 KB Guessed the password with 13638 queries.
12 Correct 138 ms 464 KB Guessed the password with 12459 queries.
13 Correct 115 ms 352 KB Guessed the password with 14392 queries.
14 Correct 115 ms 472 KB Guessed the password with 13937 queries.
15 Correct 182 ms 360 KB Guessed the password with 15073 queries.
16 Correct 179 ms 476 KB Guessed the password with 14154 queries.
17 Correct 185 ms 360 KB Guessed the password with 16054 queries.
18 Correct 124 ms 364 KB Guessed the password with 15189 queries.
19 Correct 207 ms 476 KB Guessed the password with 16410 queries.
20 Correct 172 ms 448 KB Guessed the password with 14247 queries.
21 Correct 98 ms 480 KB Guessed the password with 16849 queries.
22 Correct 160 ms 448 KB Guessed the password with 15315 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 61 queries.
2 Correct 2 ms 200 KB Guessed the password with 101 queries.
3 Correct 1 ms 200 KB Guessed the password with 49 queries.
4 Correct 1 ms 200 KB Guessed the password with 117 queries.
5 Correct 1 ms 200 KB Guessed the password with 92 queries.
6 Correct 4 ms 200 KB Guessed the password with 197 queries.
7 Correct 43 ms 432 KB Guessed the password with 3456 queries.
8 Correct 64 ms 320 KB Guessed the password with 5025 queries.
9 Correct 81 ms 464 KB Guessed the password with 6352 queries.
10 Correct 92 ms 344 KB Guessed the password with 8693 queries.
11 Correct 140 ms 468 KB Guessed the password with 13638 queries.
12 Correct 138 ms 464 KB Guessed the password with 12459 queries.
13 Correct 115 ms 352 KB Guessed the password with 14392 queries.
14 Correct 115 ms 472 KB Guessed the password with 13937 queries.
15 Correct 182 ms 360 KB Guessed the password with 15073 queries.
16 Correct 179 ms 476 KB Guessed the password with 14154 queries.
17 Correct 185 ms 360 KB Guessed the password with 16054 queries.
18 Correct 124 ms 364 KB Guessed the password with 15189 queries.
19 Correct 207 ms 476 KB Guessed the password with 16410 queries.
20 Correct 172 ms 448 KB Guessed the password with 14247 queries.
21 Correct 98 ms 480 KB Guessed the password with 16849 queries.
22 Correct 160 ms 448 KB Guessed the password with 15315 queries.
23 Correct 292 ms 428 KB Guessed the password with 23612 queries.
24 Correct 324 ms 592 KB Guessed the password with 22226 queries.
25 Correct 259 ms 456 KB Guessed the password with 23794 queries.
26 Correct 202 ms 548 KB Guessed the password with 23332 queries.
27 Correct 216 ms 408 KB Guessed the password with 23763 queries.
28 Correct 271 ms 452 KB Guessed the password with 23045 queries.
29 Correct 269 ms 568 KB Guessed the password with 23847 queries.
30 Correct 189 ms 452 KB Guessed the password with 22506 queries.