oj.uz

답안 #160330

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160330 2019-10-27T02:46:56 Z model_code Password (RMI18_password) C
80 / 100
 535 ms 380 KB 
/**
 * Like cf-n-sigma-2.c, but processes characters in increasing order of
 * frequency. The worst case requires n * sigma / 2 queries.
 *
 * Author: Catalin Francu
 **/
#include <string.h>

#define MAX_N 5000
#define MAX_SIGMA 26

char q[MAX_N + 1];
int f[MAX_SIGMA];
int n, s;

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');
}

/* find the next smallest frequency */
char findNext() {
  int pos = 0;
  for (int i = 1; i < s; i++) {
    if (f[i] < f[pos]) {
      pos = i;
    }
  }

  f[pos] = n + 1; /* so it is never found again */
  return 'a' + pos;
}

char* guess(int localN, int localS) {
  n = localN;
  s = localS;

  /* run s-1 queries to determine element frequencies */
  /* the last frequency is computed by difference */
  q[n] = '\0';
  f[0] = n;
  for (int i = 1; i < s; i++) {
    memset(q, 'a' + i, n);
    f[i] = query(q);
    f[0] -= f[i];
  }

  q[0] = '\0';

  int c = findNext(); /* 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 = findNext();
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Guessed the password with 147 queries.
2 Correct 16 ms 248 KB Guessed the password with 316 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Guessed the password with 72 queries.
2 Correct 2 ms 376 KB Guessed the password with 102 queries.
3 Correct 2 ms 248 KB Guessed the password with 96 queries.
4 Correct 4 ms 252 KB Guessed the password with 190 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 376 KB Guessed the password with 3158 queries.
2 Correct 109 ms 376 KB Guessed the password with 9678 queries.
3 Correct 52 ms 248 KB Guessed the password with 5233 queries.
4 Correct 176 ms 376 KB Guessed the password with 14046 queries.

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Guessed the password with 147 queries.
2 Correct 16 ms 248 KB Guessed the password with 316 queries.
3 Correct 3 ms 376 KB Guessed the password with 72 queries.
4 Correct 2 ms 376 KB Guessed the password with 102 queries.
5 Correct 2 ms 248 KB Guessed the password with 96 queries.
6 Correct 4 ms 252 KB Guessed the password with 190 queries.
7 Correct 39 ms 376 KB Guessed the password with 3158 queries.
8 Correct 109 ms 376 KB Guessed the password with 9678 queries.
9 Correct 52 ms 248 KB Guessed the password with 5233 queries.
10 Correct 176 ms 376 KB Guessed the password with 14046 queries.
11 Correct 105 ms 252 KB Guessed the password with 9437 queries.
12 Correct 117 ms 248 KB Guessed the password with 9476 queries.
13 Correct 233 ms 248 KB Guessed the password with 18000 queries.
14 Correct 199 ms 376 KB Guessed the password with 18375 queries.
15 Correct 167 ms 248 KB Guessed the password with 14514 queries.
16 Correct 194 ms 248 KB Guessed the password with 14405 queries.
17 Correct 160 ms 248 KB Guessed the password with 12274 queries.
18 Correct 158 ms 248 KB Guessed the password with 12343 queries.
19 Correct 114 ms 380 KB Guessed the password with 11034 queries.
20 Correct 118 ms 248 KB Guessed the password with 11258 queries.
21 Correct 163 ms 252 KB Guessed the password with 15327 queries.
22 Correct 157 ms 248 KB Guessed the password with 15391 queries.

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Guessed the password with 147 queries.
2 Correct 16 ms 248 KB Guessed the password with 316 queries.
3 Correct 3 ms 376 KB Guessed the password with 72 queries.
4 Correct 2 ms 376 KB Guessed the password with 102 queries.
5 Correct 2 ms 248 KB Guessed the password with 96 queries.
6 Correct 4 ms 252 KB Guessed the password with 190 queries.
7 Correct 39 ms 376 KB Guessed the password with 3158 queries.
8 Correct 109 ms 376 KB Guessed the password with 9678 queries.
9 Correct 52 ms 248 KB Guessed the password with 5233 queries.
10 Correct 176 ms 376 KB Guessed the password with 14046 queries.
11 Correct 105 ms 252 KB Guessed the password with 9437 queries.
12 Correct 117 ms 248 KB Guessed the password with 9476 queries.
13 Correct 233 ms 248 KB Guessed the password with 18000 queries.
14 Correct 199 ms 376 KB Guessed the password with 18375 queries.
15 Correct 167 ms 248 KB Guessed the password with 14514 queries.
16 Correct 194 ms 248 KB Guessed the password with 14405 queries.
17 Correct 160 ms 248 KB Guessed the password with 12274 queries.
18 Correct 158 ms 248 KB Guessed the password with 12343 queries.
19 Correct 114 ms 380 KB Guessed the password with 11034 queries.
20 Correct 118 ms 248 KB Guessed the password with 11258 queries.
21 Correct 163 ms 252 KB Guessed the password with 15327 queries.
22 Correct 157 ms 248 KB Guessed the password with 15391 queries.
23 Execution timed out 535 ms 304 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -