oj.uz

Submission #859830

# Submission time Handle Problem Language Result Execution time Memory
859830 2023-10-10T18:29:21 Z Andrei_Calota Password (RMI18_password) C++14
50 / 100
 819 ms 772 KB 
#include <bits/stdc++.h>

using namespace std;
const int N_MAX = 5e3;
const int SIGMA_MAX = 26;

/**int query (string candidate) {
   cout << candidate << "\n";
   int ret; cin >> ret;
   return ret;
}**/

int query (string str);

string getCopy (int letter, int f) {
    string ret = "";
    for (int i = 0; i < f; i ++)
       ret = ret + char (letter + 'a');
    return ret;
}


int freq[SIGMA_MAX];
string guess (int n, int s) {

    int steps = 0;

    int N = n, SIGMA = s;
    string aux;
    for (int letter = 0; letter < SIGMA; letter ++) {
       aux = getCopy (letter, N);
       freq[letter] = query (aux);
       steps ++;
    }

    string done = "";
    for (int pos = N - 1; pos >= 0; pos --) {
       int left = 0, right = 1;
       while (right < SIGMA) {
          if (freq[left] == 0) {
            left ++;
            right = max (right, left + 1);
            continue;
          }
          if (freq[right] == 0) {
            right ++;
            continue;
          }

          aux = getCopy (left, freq[left]);
          aux = aux + char (right + 'a');
          aux = aux + done;

          int len = query (aux);
          steps ++;
          assert (steps <= 50000);

          if (len != N && len != (int) aux.size ())
            right ++;
          else if (len != N){
            left = right;
            right ++;
          }
          else
            return aux;
       }
       done = char (left + 'a') + done;
       ///cout << "pana acum done este egal cu " << done << "\n";
       freq[left] --;
    }

    ///cout << "am termina in " << steps << "\n";

    return done;

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 121 queries.
2 Correct 1 ms 344 KB Guessed the password with 277 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 48 queries.
2 Correct 1 ms 436 KB Guessed the password with 136 queries.
3 Correct 0 ms 344 KB Guessed the password with 18 queries.
4 Correct 2 ms 344 KB Guessed the password with 295 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 764 KB Guessed the password with 9307 queries.
2 Correct 127 ms 752 KB Guessed the password with 17735 queries.
3 Correct 248 ms 508 KB Guessed the password with 20689 queries.
4 Correct 306 ms 508 KB Guessed the password with 37112 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 121 queries.
2 Correct 1 ms 344 KB Guessed the password with 277 queries.
3 Correct 1 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 436 KB Guessed the password with 136 queries.
5 Correct 0 ms 344 KB Guessed the password with 18 queries.
6 Correct 2 ms 344 KB Guessed the password with 295 queries.
7 Correct 73 ms 764 KB Guessed the password with 9307 queries.
8 Correct 127 ms 752 KB Guessed the password with 17735 queries.
9 Correct 248 ms 508 KB Guessed the password with 20689 queries.
10 Correct 306 ms 508 KB Guessed the password with 37112 queries.
11 Correct 819 ms 524 KB Guessed the password with 41054 queries.
12 Incorrect 423 ms 772 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 121 queries.
2 Correct 1 ms 344 KB Guessed the password with 277 queries.
3 Correct 1 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 436 KB Guessed the password with 136 queries.
5 Correct 0 ms 344 KB Guessed the password with 18 queries.
6 Correct 2 ms 344 KB Guessed the password with 295 queries.
7 Correct 73 ms 764 KB Guessed the password with 9307 queries.
8 Correct 127 ms 752 KB Guessed the password with 17735 queries.
9 Correct 248 ms 508 KB Guessed the password with 20689 queries.
10 Correct 306 ms 508 KB Guessed the password with 37112 queries.
11 Correct 819 ms 524 KB Guessed the password with 41054 queries.
12 Incorrect 423 ms 772 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -