Submission #858077

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858077	2023-10-07T11:51:26 Z	alexdd	Password (RMI18_password)	C++17	80 / 100	520 ms	2044 KB

password

#include<bits/stdc++.h>
using namespace std;
int query(string str);
string tostr(int x, int cnt)
{
    string cv = "";
    for(int i=0;i<cnt;i++)
        cv.push_back((char)('a'+x));
    return cv;
}
pair<int,int> v[30];
string guess(int n, int s)
{
    string aux;
    for(int i=0;i<s;i++)
    {
        aux = tostr(i, n);
        v[i]={query(aux), i};
    }
    sort(v,v+s);
    string rez="";
    for(int i=0;i<s;i++)
    {
        int cnt = v[i].first;
        int x = v[i].second;
        if(cnt==0)
            continue;
        if((int)rez.size()==0)
        {
            rez = tostr(x, cnt);
            continue;
        }
        string newrez="";

        int nr = query(rez + tostr(x, n - (int)rez.size())) - (int)rez.size();
        newrez = newrez + tostr(x, nr);
        int suff = nr;
        for(int j=(int)rez.size()-1;j>=0;j--)
        {
            int nr = (query(rez.substr(0,j) + tostr(x, n - (int)rez.size())) - j) - suff;
            newrez = newrez + rez[j] + tostr(x, nr);
            suff = nr + suff;
        }
        reverse(newrez.begin(),newrez.end());
        rez = newrez;
    }
    return rez;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Guessed the password with 135 queries.
2	Correct	1 ms	344 KB	Guessed the password with 299 queries.

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Guessed the password with 28 queries.
2	Correct	0 ms	344 KB	Guessed the password with 34 queries.
3	Correct	0 ms	344 KB	Guessed the password with 20 queries.
4	Correct	1 ms	436 KB	Guessed the password with 93 queries.

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1208 KB	Guessed the password with 2160 queries.
2	Correct	50 ms	732 KB	Guessed the password with 8449 queries.
3	Correct	24 ms	964 KB	Guessed the password with 3638 queries.
4	Correct	86 ms	976 KB	Guessed the password with 12061 queries.

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Guessed the password with 135 queries.
2	Correct	1 ms	344 KB	Guessed the password with 299 queries.
3	Correct	1 ms	344 KB	Guessed the password with 28 queries.
4	Correct	0 ms	344 KB	Guessed the password with 34 queries.
5	Correct	0 ms	344 KB	Guessed the password with 20 queries.
6	Correct	1 ms	436 KB	Guessed the password with 93 queries.
7	Correct	12 ms	1208 KB	Guessed the password with 2160 queries.
8	Correct	50 ms	732 KB	Guessed the password with 8449 queries.
9	Correct	24 ms	964 KB	Guessed the password with 3638 queries.
10	Correct	86 ms	976 KB	Guessed the password with 12061 queries.
11	Correct	54 ms	684 KB	Guessed the password with 6648 queries.
12	Correct	55 ms	952 KB	Guessed the password with 6681 queries.
13	Correct	120 ms	700 KB	Guessed the password with 15007 queries.
14	Correct	123 ms	708 KB	Guessed the password with 15385 queries.
15	Correct	93 ms	956 KB	Guessed the password with 11319 queries.
16	Correct	92 ms	756 KB	Guessed the password with 11223 queries.
17	Correct	78 ms	704 KB	Guessed the password with 8978 queries.
18	Correct	78 ms	504 KB	Guessed the password with 9060 queries.
19	Correct	62 ms	504 KB	Guessed the password with 7637 queries.
20	Correct	65 ms	748 KB	Guessed the password with 7860 queries.
21	Correct	98 ms	508 KB	Guessed the password with 11829 queries.
22	Correct	95 ms	1012 KB	Guessed the password with 11947 queries.

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Guessed the password with 135 queries.
2	Correct	1 ms	344 KB	Guessed the password with 299 queries.
3	Correct	1 ms	344 KB	Guessed the password with 28 queries.
4	Correct	0 ms	344 KB	Guessed the password with 34 queries.
5	Correct	0 ms	344 KB	Guessed the password with 20 queries.
6	Correct	1 ms	436 KB	Guessed the password with 93 queries.
7	Correct	12 ms	1208 KB	Guessed the password with 2160 queries.
8	Correct	50 ms	732 KB	Guessed the password with 8449 queries.
9	Correct	24 ms	964 KB	Guessed the password with 3638 queries.
10	Correct	86 ms	976 KB	Guessed the password with 12061 queries.
11	Correct	54 ms	684 KB	Guessed the password with 6648 queries.
12	Correct	55 ms	952 KB	Guessed the password with 6681 queries.
13	Correct	120 ms	700 KB	Guessed the password with 15007 queries.
14	Correct	123 ms	708 KB	Guessed the password with 15385 queries.
15	Correct	93 ms	956 KB	Guessed the password with 11319 queries.
16	Correct	92 ms	756 KB	Guessed the password with 11223 queries.
17	Correct	78 ms	704 KB	Guessed the password with 8978 queries.
18	Correct	78 ms	504 KB	Guessed the password with 9060 queries.
19	Correct	62 ms	504 KB	Guessed the password with 7637 queries.
20	Correct	65 ms	748 KB	Guessed the password with 7860 queries.
21	Correct	98 ms	508 KB	Guessed the password with 11829 queries.
22	Correct	95 ms	1012 KB	Guessed the password with 11947 queries.
23	Incorrect	520 ms	2044 KB	Could not guess the password with 50000 queries.
24	Halted	0 ms	0 KB	-