oj.uz

Submission #160329

# Submission time Handle Problem Language Result Execution time Memory
160329 2019-10-27T02:46:41 Z model_code Password (RMI18_password) C
50 / 100
 536 ms 380 KB 
/**
 * Fill in one symbol at the time. To guess the placements of next symbol X,
 * consider every gap between characters in existing string and insert X's
 * until the answer stops increasing.
 *
 * Running time: O(|Q| + 1 + freq[X]) for every X. If we work out the math:
 *
 * - The frequencies sum up to n.
 * - The 1's sum up to sigma.
 * - The |Q| at each step is the sum of frequencies of previous symbols.
 * - Thus the worst case is freq[a] = n - sigma + 1, freq[b..z] = 1,
 *   which takes n * sigma queries (give or take).
 * - For equal frequencies (freq[X] = n / sigma), n * sigma / 2 queries are
 *   needed.
 *
 * Author: Catalin Francu
 **/
#include <string.h>

#define MAX_N 5000

char q[MAX_N + 1];

int query(char *q);

void shiftRight(char *s) {
  char save = *s;
  do {
    int tmp = save;
    save = *(s + 1);
    *(s + 1) = tmp;
    s++;
  } while (*s != '\0');
}

void shiftLeft(char *s) {
  do {
    *(s - 1) = *s;
    s++;
  } while (*(s - 1) != '\0');
}

char* guess(int n, int s) {
  /* we don't use s */

  q[0] = '\0';

  int c = 'a'; /* current symbol being inserted */
  int answer = 0;
  int pos = 0;
  int len = 0; /* length of current string */

  while (answer < n) {
    /* roll back the last change and move on if answer != len */
    if (answer != len) {
      shiftLeft(q + pos);
      len--;

      if (q[pos - 1] == '\0') {
        /* move on to the next symbol */
        c++;
        pos = 0;
      }
      /* otherwise leave pos unchanged, which skips one symbol < c */
    }

    /* insert another copy of c at position pos */
    shiftRight(q + pos);
    q[pos++] = c;
    len++;

    answer = query(q);
  }

  return q;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Guessed the password with 71 queries.
2 Correct 4 ms 252 KB Guessed the password with 166 queries.
3 Correct 3 ms 328 KB Guessed the password with 102 queries.
4 Correct 3 ms 240 KB Guessed the password with 228 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 308 KB Guessed the password with 4807 queries.
2 Correct 112 ms 296 KB Guessed the password with 10754 queries.
3 Correct 136 ms 296 KB Guessed the password with 14365 queries.
4 Correct 239 ms 380 KB Guessed the password with 20878 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Guessed the password with 133 queries.
2 Correct 3 ms 248 KB Guessed the password with 294 queries.
3 Correct 3 ms 248 KB Guessed the password with 71 queries.
4 Correct 4 ms 252 KB Guessed the password with 166 queries.
5 Correct 3 ms 328 KB Guessed the password with 102 queries.
6 Correct 3 ms 240 KB Guessed the password with 228 queries.
7 Correct 47 ms 308 KB Guessed the password with 4807 queries.
8 Correct 112 ms 296 KB Guessed the password with 10754 queries.
9 Correct 136 ms 296 KB Guessed the password with 14365 queries.
10 Correct 239 ms 380 KB Guessed the password with 20878 queries.
11 Execution timed out 536 ms 296 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 133 queries.
2 Correct 3 ms 248 KB Guessed the password with 294 queries.
3 Correct 3 ms 248 KB Guessed the password with 71 queries.
4 Correct 4 ms 252 KB Guessed the password with 166 queries.
5 Correct 3 ms 328 KB Guessed the password with 102 queries.
6 Correct 3 ms 240 KB Guessed the password with 228 queries.
7 Correct 47 ms 308 KB Guessed the password with 4807 queries.
8 Correct 112 ms 296 KB Guessed the password with 10754 queries.
9 Correct 136 ms 296 KB Guessed the password with 14365 queries.
10 Correct 239 ms 380 KB Guessed the password with 20878 queries.
11 Execution timed out 536 ms 296 KB Time limit exceeded (wall clock)
12 Halted 0 ms 0 KB -