oj.uz

Submission #160327

# Submission time Handle Problem Language Result Execution time Memory
160327 2019-10-27T02:36:48 Z model_code Password (RMI18_password) C
50 / 100
 446 ms 444 KB 
/**
 * Fill in one symbol at the time. To guess the placements of next symbol X,
 * take each prefix of the existing string and pad it with X's to length n.
 *
 * Queries: n x sigma
 *
 * Author: Catalin Francu
 **/
#include <string.h>

#define MAX_N 5000

char q[MAX_N + 1];
char qc[MAX_N + 1]; /* copy of c */
int answer[MAX_N + 1];

int query(char *q);

char* guess(int n, int s) {
  q[0] = '\0';
  int qlen = 0;

  for (int c = 'a'; c < 'a' + s; c++) {
    strcpy(qc, q);

    for (int i = qlen; i < n; i++) {
      q[i] = c;
    }
    q[n] = 0;

    for (int i = qlen; i >= 0; i--) {
      q[i] = c;
      answer[i] = query(q) - i; /* count only the c's, not the prefix */
    }

    /* rebuild q from qc interleaved with occurrences of c */
    int newlen = 0;
    for (int i = 0; i <= qlen; i++) {
      for (int j = 0; j < answer[i] - answer[i + 1]; j++) {
        q[newlen++] = c;
      }
      if (i < qlen) {
        q[newlen++] = qc[i];
      }
    }
    q[newlen] = 0;
    qlen = newlen;
  }

  return q;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 312 KB Guessed the password with 3818 queries.
2 Correct 120 ms 320 KB Guessed the password with 9474 queries.
3 Correct 145 ms 376 KB Guessed the password with 12785 queries.
4 Correct 213 ms 444 KB Guessed the password with 18895 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Guessed the password with 121 queries.
2 Correct 5 ms 248 KB Guessed the password with 277 queries.
3 Correct 2 ms 296 KB Guessed the password with 27 queries.
4 Correct 2 ms 388 KB Guessed the password with 106 queries.
5 Correct 2 ms 248 KB Guessed the password with 26 queries.
6 Correct 3 ms 376 KB Guessed the password with 133 queries.
7 Correct 45 ms 312 KB Guessed the password with 3818 queries.
8 Correct 120 ms 320 KB Guessed the password with 9474 queries.
9 Correct 145 ms 376 KB Guessed the password with 12785 queries.
10 Correct 213 ms 444 KB Guessed the password with 18895 queries.
11 Execution timed out 446 ms 444 KB Time limit exceeded (wall clock)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Guessed the password with 121 queries.
2 Correct 5 ms 248 KB Guessed the password with 277 queries.
3 Correct 2 ms 296 KB Guessed the password with 27 queries.
4 Correct 2 ms 388 KB Guessed the password with 106 queries.
5 Correct 2 ms 248 KB Guessed the password with 26 queries.
6 Correct 3 ms 376 KB Guessed the password with 133 queries.
7 Correct 45 ms 312 KB Guessed the password with 3818 queries.
8 Correct 120 ms 320 KB Guessed the password with 9474 queries.
9 Correct 145 ms 376 KB Guessed the password with 12785 queries.
10 Correct 213 ms 444 KB Guessed the password with 18895 queries.
11 Execution timed out 446 ms 444 KB Time limit exceeded (wall clock)
12 Halted 0 ms 0 KB -