oj.uz

Submission #476230

# Submission time Handle Problem Language Result Execution time Memory
476230 2021-09-25T13:11:32 Z iulia13 Password (RMI18_password) C++14
50 / 100
 398 ms 300 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();

  // validation


  // while possible, advance one character in q and find its next
  // occurrence in password
  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 guess(int n, int s)
{
    char a;
    int q = 0;
    for (int i = 0; i < s; i++)
    {
        a = 'a' + i;
        p = ans;
        for (int j = q; j < n; j++)
            p += a;
        for (int h = q; h >= 0; h--)
        {
            cnt[h] = query(p) - h;
            if (h)
                p[h - 1] = a;
        }
        int nq = 0;
        prov = "";
        for (int j = 0; j <= q; j++)
        {
            int x = cnt[j] - cnt[j + 1];
            while(x--)
            {
                prov += a;
                nq++;
            }
            if (j != q)
            {
                prov += ans[j];
                nq++;
            }
        }
        q = nq;
        ans = prov;
    }
    return ans;
}/*
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 3 ms 200 KB Guessed the password with 121 queries.
2 Correct 4 ms 200 KB Guessed the password with 277 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 27 queries.
2 Correct 1 ms 200 KB Guessed the password with 106 queries.
3 Correct 1 ms 200 KB Guessed the password with 26 queries.
4 Correct 2 ms 200 KB Guessed the password with 133 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 280 KB Guessed the password with 3818 queries.
2 Correct 125 ms 288 KB Guessed the password with 9474 queries.
3 Correct 144 ms 284 KB Guessed the password with 12785 queries.
4 Correct 171 ms 296 KB Guessed the password with 18895 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 121 queries.
2 Correct 4 ms 200 KB Guessed the password with 277 queries.
3 Correct 1 ms 200 KB Guessed the password with 27 queries.
4 Correct 1 ms 200 KB Guessed the password with 106 queries.
5 Correct 1 ms 200 KB Guessed the password with 26 queries.
6 Correct 2 ms 200 KB Guessed the password with 133 queries.
7 Correct 48 ms 280 KB Guessed the password with 3818 queries.
8 Correct 125 ms 288 KB Guessed the password with 9474 queries.
9 Correct 144 ms 284 KB Guessed the password with 12785 queries.
10 Correct 171 ms 296 KB Guessed the password with 18895 queries.
11 Incorrect 398 ms 300 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 121 queries.
2 Correct 4 ms 200 KB Guessed the password with 277 queries.
3 Correct 1 ms 200 KB Guessed the password with 27 queries.
4 Correct 1 ms 200 KB Guessed the password with 106 queries.
5 Correct 1 ms 200 KB Guessed the password with 26 queries.
6 Correct 2 ms 200 KB Guessed the password with 133 queries.
7 Correct 48 ms 280 KB Guessed the password with 3818 queries.
8 Correct 125 ms 288 KB Guessed the password with 9474 queries.
9 Correct 144 ms 284 KB Guessed the password with 12785 queries.
10 Correct 171 ms 296 KB Guessed the password with 18895 queries.
11 Incorrect 398 ms 300 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -