| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1327270 | dashka | Password (RMI18_password) | C++20 | 0 ms | 0 KiB |
/**
* 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;
}