Submission #160330

#	Time	Username	Problem	Language	Result	Execution time	Memory
160330		model_code	Password (RMI18_password)	C11	80 / 100	535 ms	380 KiB

password

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