제출 #160328

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

password

/**
 * Count symbol frequencies. Start with sigma strings, each holding all
 * occurrences of one symbol. At each step, take the two shortest strings and
 * merge them.
 *
 * Each query merges exactly one symbol and each symbol is merged at most log
 * sigma times, so the number of queries is sigma + n log sigma.
 *
 * The implementation keeps an array of char pointers sorted by length. This
 * could obviously be improved using a heap.
 *
 * Author: Catalin Francu
 **/
#include <stdlib.h>
#include <string.h>

#define MAX_N 5000
#define MAX_SIGMA 26

typedef struct {
  char *s;
  int len;
} string;

char buf[MAX_SIGMA][MAX_N + 1];
string str[MAX_SIGMA];
char q[MAX_N + 1];    /* merging happens here */
int n, s, ns; /* ns = number of strings still to merge */

int query(char *q);

/* empty strings are allowed; they will simply be merged with no queries */
void addSingleLetterString(int pos, int len) {
  memset(buf[ns], 'a' + pos, len);
  buf[ns][len] = '\0';
  str[ns] = (string) { buf[ns], len };
  ns++;
}

/* run s-1 queries to determine element frequencies; */
/* the last frequency is computed by difference */
void findFrequencies() {
  int remainder = n, answer;

  q[n] = '\0';
  for (int i = 0; i < s - 1; i++) {
    memset(q, 'a' + i, n);
    answer = query(q);
    addSingleLetterString(i, answer);
    remainder -= answer;
  }

  addSingleLetterString(s - 1, remainder);
}

int cmpLen(const void *a, const void *b) {
  return ((string*)b)->len - ((string*)a)->len;
}

/* move str[n - 1] left so str is sorted by length */
void migrate() {
  int i = ns - 1;
  while (i && (str[i].len > str[i - 1].len)) {
    string tmp = str[i];
    str[i] = str[i - 1];
    str[i - 1] = tmp;
    i--;
  }
}

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

  findFrequencies();
  qsort(str, ns, sizeof(string), cmpLen);

  while (ns > 1) {
    /* merge the last two strings using q for queries */
    char *x = str[ns - 1].s, *y = str[ns - 2].s; /* head pointers */
    char *xc = x, *yc = y, *qc = q; /* current pointers */
    *q = '\0';

    while (*xc && *yc) {
      /* copy one symbol from x and all the symbols from y */
      *qc = *xc;
      strcpy(qc + 1, yc);
      if (query(q) == str[ns - 2].len + (xc - x + 1)) {
        xc++;
      } else {
        *qc = *yc;
        yc++;
      }
      qc++;
    }

    /* copy remainders of x and y */
    strcpy(qc, xc);
    qc = q + str[ns - 1].len + (yc - y);
    strcpy(qc, yc);

    /* remove the original strings and add the merged string */
    strcpy(str[ns - 2].s, q);
    str[ns - 2].len += str[ns - 1].len;
    ns--;
    migrate();
  }

  return str[0].s;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20