Submission #1338531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338531		aaaaaaaa	Password (RMI18_password)	C++20	0 / 100	1 ms	344 KiB

password

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

int query(string str);

string guess(int n, int s){
    vector<int> freq(s, 0);
    int used = 0;

    for(int c = 0; c < s; c++){
        int low = 0, high = n - used;
        int best = 0;

        while(low <= high){
            int mid = (low + high) / 2;
            string test(mid, 'a' + c);
            int res = query(test);

            if(res == mid){
                best = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        freq[c] = best;
        used += best;
    }

    string ans = "";

    for(int c = 0; c < s; c++){
        int f = freq[c];
        if(f == 0) continue;

        if(ans.empty()){
            ans = string(f, 'a' + c);
            continue;
        }

        int m = ans.size();
        vector<int> add(m + 1, 0);
        int remaining = f;

        vector<int> order(m + 1);
        iota(order.begin(), order.end(), 0);
        random_shuffle(order.begin(), order.end());

        for(int idx : order){
            int lo = 0, hi = remaining, best_add = 0;

            while(lo <= hi){
                int mid = (lo + hi) / 2;

                string cur = "";
                for(int i = 0; i <= m; i++){
                    if(i < m) cur += ans[i];
                    if(i == idx) cur += string(mid, 'a' + c);
                }

                int res = query(cur);
                if(res == (int)cur.size()){
                    best_add = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }

            add[idx] = best_add;
            remaining -= best_add;
            if(remaining == 0) break;
        }

        string new_ans = "";
        for(int i = 0; i <= m; i++){
            if(i < m) new_ans += ans[i];
            new_ans += string(add[i], 'a' + c);
        }
        ans = new_ans;
    }

    return ans;
}

Compilation message (stderr)

password.cpp: In function 'std::string guess(int, int)':
password.cpp:48:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   48 |         random_shuffle(order.begin(), order.end());
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from password.cpp:1:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

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