Submission #858097

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858097	2023-10-07T12:00:17 Z	alexdd	Password (RMI18_password)	C++17	80 / 100	476 ms	2088 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;
        }
        if((int)rez.size()==n)
            break;
        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--)
        {
            if((int)newrez.size()==n)
                break;
            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	0 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	428 KB	Guessed the password with 93 queries.

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	1232 KB	Guessed the password with 2160 queries.
2	Correct	50 ms	856 KB	Guessed the password with 8449 queries.
3	Correct	22 ms	1208 KB	Guessed the password with 3638 queries.
4	Correct	81 ms	980 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	0 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	428 KB	Guessed the password with 93 queries.
7	Correct	11 ms	1232 KB	Guessed the password with 2160 queries.
8	Correct	50 ms	856 KB	Guessed the password with 8449 queries.
9	Correct	22 ms	1208 KB	Guessed the password with 3638 queries.
10	Correct	81 ms	980 KB	Guessed the password with 12061 queries.
11	Correct	54 ms	700 KB	Guessed the password with 6648 queries.
12	Correct	51 ms	1204 KB	Guessed the password with 6681 queries.
13	Correct	123 ms	964 KB	Guessed the password with 15007 queries.
14	Correct	112 ms	1232 KB	Guessed the password with 15385 queries.
15	Correct	89 ms	1200 KB	Guessed the password with 11319 queries.
16	Correct	91 ms	956 KB	Guessed the password with 11223 queries.
17	Correct	68 ms	988 KB	Guessed the password with 8978 queries.
18	Correct	73 ms	740 KB	Guessed the password with 9060 queries.
19	Correct	65 ms	1248 KB	Guessed the password with 7637 queries.
20	Correct	71 ms	760 KB	Guessed the password with 7860 queries.
21	Correct	95 ms	1232 KB	Guessed the password with 11829 queries.
22	Correct	102 ms	948 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	0 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	428 KB	Guessed the password with 93 queries.
7	Correct	11 ms	1232 KB	Guessed the password with 2160 queries.
8	Correct	50 ms	856 KB	Guessed the password with 8449 queries.
9	Correct	22 ms	1208 KB	Guessed the password with 3638 queries.
10	Correct	81 ms	980 KB	Guessed the password with 12061 queries.
11	Correct	54 ms	700 KB	Guessed the password with 6648 queries.
12	Correct	51 ms	1204 KB	Guessed the password with 6681 queries.
13	Correct	123 ms	964 KB	Guessed the password with 15007 queries.
14	Correct	112 ms	1232 KB	Guessed the password with 15385 queries.
15	Correct	89 ms	1200 KB	Guessed the password with 11319 queries.
16	Correct	91 ms	956 KB	Guessed the password with 11223 queries.
17	Correct	68 ms	988 KB	Guessed the password with 8978 queries.
18	Correct	73 ms	740 KB	Guessed the password with 9060 queries.
19	Correct	65 ms	1248 KB	Guessed the password with 7637 queries.
20	Correct	71 ms	760 KB	Guessed the password with 7860 queries.
21	Correct	95 ms	1232 KB	Guessed the password with 11829 queries.
22	Correct	102 ms	948 KB	Guessed the password with 11947 queries.
23	Incorrect	476 ms	2088 KB	Could not guess the password with 50000 queries.
24	Halted	0 ms	0 KB	-