#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>
// Declaration of query. This must be defined elsewhere.
int query(const char *p);
//----------------------------------------------------------------
// Helper function: ck
// This function builds a temporary string t as follows:
// 1. t[0] is the character c.
// 2. For indices 0 to (ans_len - l - 1) of ans, if ans[i]==c, append c.
// 3. Then append ans[i] for i from (ans_len - l) to (ans_len - 1).
// It returns true if query(t) equals the length of t.
static bool ck(char c, int l, const char *ans, int ans_len) {
// Maximum possible length of t is (ans_len + 1)
int t_buf_size = ans_len + 2;
char *t_buf = malloc(t_buf_size);
if (!t_buf) {
fprintf(stderr, "malloc failed in ck\n");
exit(1);
}
int t_len = 0;
t_buf[t_len++] = c;
// Append copies of c for every ans[i]==c in the first part.
for (int i = 0; i < ans_len - l; i++) {
if (ans[i] == c) {
t_buf[t_len++] = c;
}
}
// Append the tail of ans.
for (int i = ans_len - l; i < ans_len; i++) {
t_buf[t_len++] = ans[i];
}
t_buf[t_len] = '\0';
int res = query(t_buf);
free(t_buf);
return (res == t_len);
}
//----------------------------------------------------------------
// Function: guess
// Parameters:
// n - the final length of the answer string
// s - the number of distinct letters to consider (assumed to be consecutive letters starting from 'a')
// Returns a malloc’ed string of length n (caller is responsible for freeing it).
char* guess(int n, int s) {
// Allocate buffer for the final answer; we build it gradually.
char *ans = malloc(n + 1);
if (!ans) {
fprintf(stderr, "malloc failed for ans\n");
exit(1);
}
int ans_len = 0;
// Allocate and zero-initialize an array of s integers.
int *cnt = calloc(s, sizeof(int));
if (!cnt) {
fprintf(stderr, "calloc failed for cnt\n");
exit(1);
}
// For each letter from 'a' to 'a' + s - 1, try to build a string "cur" of that letter.
for (int i = 0; i < s; i++) {
char c = 'a' + i;
char cur[n + 1]; // temporary buffer (max length n)
int cur_len = 0;
while (cur_len < n) {
cur[cur_len] = c;
cur[cur_len + 1] = '\0';
if (query(cur) != cur_len + 1) {
break;
}
cur_len++;
}
cnt[i] = cur_len;
}
// Find the first letter that produced a nonzero count.
int st = -1;
for (int i = 0; i < s; i++) {
if (cnt[i] != 0) {
char c = 'a' + i;
for (int j = 0; j < cnt[i]; j++) {
ans[ans_len++] = c;
}
st = i;
break;
}
}
// For each remaining letter, adjust ans using a binary search strategy.
for (int i = st + 1; i < s; i++) {
for (int j = 0; j < cnt[i]; j++) {
char c = 'a' + i;
int l = 1, r = ans_len, cc = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (ck(c, mid, ans, ans_len)) {
cc = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
// Build the new answer _ans.
int new_len = ans_len + 1;
char *new_ans = malloc(new_len + 1);
if (!new_ans) {
fprintf(stderr, "malloc failed for new_ans\n");
exit(1);
}
int idx = 0;
// Copy characters from ans in reverse order from index (ans_len - 1) downto (ans_len - cc).
for (int k = ans_len - 1; k >= ans_len - cc; k--) {
new_ans[idx++] = ans[k];
}
new_ans[idx++] = c;
// Copy the remaining part of ans (from index ans_len - cc - 1 downto 0).
for (int k = ans_len - cc - 1; k >= 0; k--) {
new_ans[idx++] = ans[k];
}
// Reverse new_ans to obtain the correct order.
for (int k = 0; k < new_len / 2; k++) {
char temp = new_ans[k];
new_ans[k] = new_ans[new_len - 1 - k];
new_ans[new_len - 1 - k] = temp;
}
free(ans);
ans = new_ans;
ans_len = new_len;
}
}
// Ensure we reached the required length.
assert(ans_len == n);
ans[ans_len] = '\0';
free(cnt);
return ans;
}
