oj.uz

Submission #160331

# Submission time Handle Problem Language Result Execution time Memory
160331 2019-10-27T02:47:06 Z model_code Password (RMI18_password) C
30 / 100
 389 ms 376 KB 
/**
 * Guess one character at the time. To guess the next character, try to insert
 * every character in sigma at every position in the current query.
 *
 * Queries: n^2 sigma, but somewhat better in practice
 *
 * Author: Catalin Francu
 **/
#define MAX_N 5000

char q[MAX_N + 1]; /* initially empty */

int query(char *q);

char* guess(int n, int s) {
  for (int l = 1; l <= n; l++) {
    /* Guess one more character. Start from the end and work backwards */
    q[l] = '\0';
    int pos = l - 1, c = 'a', answer;

    do {
      q[pos] = c;
      answer = query(q);

      if (answer != l) {
        c++;
        if (c >= 'a' + s) {
          c = 'a';
          q[pos] = q[pos - 1];
          pos--;
        }
      }
    } while (answer < l);
  }

  return q;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 248 KB Guessed the password with 1335 queries.
2 Correct 54 ms 248 KB Guessed the password with 4968 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 256 KB Guessed the password with 1618 queries.
2 Correct 26 ms 248 KB Guessed the password with 2403 queries.
3 Correct 22 ms 252 KB Guessed the password with 3056 queries.
4 Correct 147 ms 376 KB Guessed the password with 15480 queries.

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 389 ms 376 KB Could not guess the password with 50000 queries.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 248 KB Guessed the password with 1335 queries.
2 Correct 54 ms 248 KB Guessed the password with 4968 queries.
3 Correct 17 ms 256 KB Guessed the password with 1618 queries.
4 Correct 26 ms 248 KB Guessed the password with 2403 queries.
5 Correct 22 ms 252 KB Guessed the password with 3056 queries.
6 Correct 147 ms 376 KB Guessed the password with 15480 queries.
7 Incorrect 389 ms 376 KB Could not guess the password with 50000 queries.
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 248 KB Guessed the password with 1335 queries.
2 Correct 54 ms 248 KB Guessed the password with 4968 queries.
3 Correct 17 ms 256 KB Guessed the password with 1618 queries.
4 Correct 26 ms 248 KB Guessed the password with 2403 queries.
5 Correct 22 ms 252 KB Guessed the password with 3056 queries.
6 Correct 147 ms 376 KB Guessed the password with 15480 queries.
7 Incorrect 389 ms 376 KB Could not guess the password with 50000 queries.
8 Halted 0 ms 0 KB -