oj.uz

Submission #160328

# Submission time Handle Problem Language Result Execution time Memory
160328 2019-10-27T02:39:33 Z model_code Password (RMI18_password) C
100 / 100
 293 ms 656 KB 
/**
 * 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 436 KB Guessed the password with 56 queries.
2 Correct 2 ms 392 KB Guessed the password with 102 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Guessed the password with 48 queries.
2 Correct 3 ms 308 KB Guessed the password with 89 queries.
3 Correct 3 ms 248 KB Guessed the password with 91 queries.
4 Correct 4 ms 296 KB Guessed the password with 177 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 348 KB Guessed the password with 2749 queries.
2 Correct 44 ms 380 KB Guessed the password with 5069 queries.
3 Correct 32 ms 376 KB Guessed the password with 4587 queries.
4 Correct 86 ms 472 KB Guessed the password with 8083 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 436 KB Guessed the password with 56 queries.
2 Correct 2 ms 392 KB Guessed the password with 102 queries.
3 Correct 2 ms 248 KB Guessed the password with 48 queries.
4 Correct 3 ms 308 KB Guessed the password with 89 queries.
5 Correct 3 ms 248 KB Guessed the password with 91 queries.
6 Correct 4 ms 296 KB Guessed the password with 177 queries.
7 Correct 35 ms 348 KB Guessed the password with 2749 queries.
8 Correct 44 ms 380 KB Guessed the password with 5069 queries.
9 Correct 32 ms 376 KB Guessed the password with 4587 queries.
10 Correct 86 ms 472 KB Guessed the password with 8083 queries.
11 Correct 84 ms 404 KB Guessed the password with 8156 queries.
12 Correct 91 ms 376 KB Guessed the password with 8161 queries.
13 Correct 135 ms 380 KB Guessed the password with 11501 queries.
14 Correct 117 ms 404 KB Guessed the password with 11601 queries.
15 Correct 114 ms 376 KB Guessed the password with 10879 queries.
16 Correct 110 ms 384 KB Guessed the password with 10861 queries.
17 Correct 104 ms 376 KB Guessed the password with 10208 queries.
18 Correct 100 ms 304 KB Guessed the password with 10245 queries.
19 Correct 120 ms 376 KB Guessed the password with 9687 queries.
20 Correct 108 ms 304 KB Guessed the password with 9773 queries.
21 Correct 110 ms 528 KB Guessed the password with 11639 queries.
22 Correct 123 ms 376 KB Guessed the password with 11707 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 436 KB Guessed the password with 56 queries.
2 Correct 2 ms 392 KB Guessed the password with 102 queries.
3 Correct 2 ms 248 KB Guessed the password with 48 queries.
4 Correct 3 ms 308 KB Guessed the password with 89 queries.
5 Correct 3 ms 248 KB Guessed the password with 91 queries.
6 Correct 4 ms 296 KB Guessed the password with 177 queries.
7 Correct 35 ms 348 KB Guessed the password with 2749 queries.
8 Correct 44 ms 380 KB Guessed the password with 5069 queries.
9 Correct 32 ms 376 KB Guessed the password with 4587 queries.
10 Correct 86 ms 472 KB Guessed the password with 8083 queries.
11 Correct 84 ms 404 KB Guessed the password with 8156 queries.
12 Correct 91 ms 376 KB Guessed the password with 8161 queries.
13 Correct 135 ms 380 KB Guessed the password with 11501 queries.
14 Correct 117 ms 404 KB Guessed the password with 11601 queries.
15 Correct 114 ms 376 KB Guessed the password with 10879 queries.
16 Correct 110 ms 384 KB Guessed the password with 10861 queries.
17 Correct 104 ms 376 KB Guessed the password with 10208 queries.
18 Correct 100 ms 304 KB Guessed the password with 10245 queries.
19 Correct 120 ms 376 KB Guessed the password with 9687 queries.
20 Correct 108 ms 304 KB Guessed the password with 9773 queries.
21 Correct 110 ms 528 KB Guessed the password with 11639 queries.
22 Correct 123 ms 376 KB Guessed the password with 11707 queries.
23 Correct 293 ms 444 KB Guessed the password with 23634 queries.
24 Correct 252 ms 608 KB Guessed the password with 20964 queries.
25 Correct 286 ms 596 KB Guessed the password with 23668 queries.
26 Correct 224 ms 532 KB Guessed the password with 19099 queries.
27 Correct 275 ms 416 KB Guessed the password with 23719 queries.
28 Correct 193 ms 656 KB Guessed the password with 16820 queries.
29 Correct 246 ms 568 KB Guessed the password with 23712 queries.
30 Correct 168 ms 444 KB Guessed the password with 14390 queries.