제출 #160327

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

password

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