제출 #160329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160329		model_code	Password (RMI18_password)	C11	50 / 100	536 ms	380 KiB

password

/**
 * 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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20