Submission #251486

#	Time	Username	Problem	Language	Result	Execution time	Memory
251486		cheeheng	Password (RMI18_password)	C++14	100 / 100	338 ms	732 KiB

password

#include <bits/stdc++.h>
using namespace std;

int query(string q);

int cnt[29];

string rec(int s, int e){
    //printf("rec(%d, %d)\n", s, e);
    if(s == e){
        string temp = "";
        for(int i = 0; i < cnt[s]; i ++){
            temp += (char)('a'+s);
        }
        return temp;
    }else{
        int m = (s+e)>>1;
        string str1 = rec(s, m);
        string str2 = rec(m+1, e);

        string res = "";
        int indx1 = 0;
        int indx2 = 0;

        int len1 = str1.size();
        int len2 = str2.size();
        while(indx1 < len1 || indx2 < len2){
            //printf("indx1=%d indx2=%d\n", indx1, indx2);
            if(indx1 == len1){
                res += str2[indx2++];
            }else if(indx2 == len2){
                res += str1[indx1++];
            }else{
                string temp = res + str1[indx1] + str2.substr(indx2, len2-indx2);
                int qres = query(temp);
                if(qres == (int)temp.size()){
                    res += str1[indx1++];
                }else{
                    res += str2[indx2++];
                }
            }
        }

        return res;
    }
}

string guess(int n, int s){
    for(int i = 0; i < s; i ++){
        string temp = "";
        for(int j = 0; j < n; j ++){
            temp += (char)('a'+i);
        }
        cnt[i] = query(temp);
    }

    return rec(0, s-1);
}

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