Submission #1162620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162620		cnn008	Password (RMI18_password)	C11	0 / 100	48 ms	464 KiB

password

#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;
}

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