oj.uz

Submission #201149

# Submission time Handle Problem Language Result Execution time Memory
201149 2020-02-09T12:46:45 Z Atill83 Password (RMI18_password) C++14
100 / 100
 299 ms 688 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

int query(string str);

pair<int, char> freq[30];

string solve(int l, int r){
    if(l == r){
        string a;
        for(int i = 0; i < freq[l].ff; i++) a += freq[l].ss;
        return a;
    }
    int m = (l + r) / 2;
    string a = solve(l, m), b = solve(m + 1, r);
    string ans;
    int l1 = 0, l2 = 0;
    while(l1 != a.length() && l2 != b.length()){
        int len = ans.length() + b.length() - l2 + 1;
        if(query(ans + a[l1] + b.substr(l2)) == len){
            ans += a[l1++];
        }else{
            ans += b[l2++];
        }
    }
    if(l1 < a.length()){
        for(int i = l1; i < a.length(); i++)
            ans +=a[i];
    }else{
        for(int i = l2; i < b.length(); i++)
            ans += b[i];
    }

    return ans;
}


string guess(int n, int s){
    int sum = 0;
    for(int i = 0; i < s - 1; i ++){
        string que;
        for(int j = 0; j < n; j++)
            que += (char)('a' + i);
        freq[i].ff = query(que);
        sum += freq[i].ff;
        freq[i].ss = (char)('a' + i);
    }
    freq[s - 1].ff = n - sum;
    freq[s - 1].ss = (char)('a' + s - 1);
    sort(freq, freq + s);
    return solve(0, s - 1);
}

Compilation message

password.cpp: In function 'std::__cxx11::string solve(int, int)':
password.cpp:20:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(l1 != a.length() && l2 != b.length()){
           ~~~^~~~~~~~~~~~~
password.cpp:20:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(l1 != a.length() && l2 != b.length()){
                               ~~~^~~~~~~~~~~~~
password.cpp:28:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(l1 < a.length()){
        ~~~^~~~~~~~~~~~
password.cpp:29:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = l1; i < a.length(); i++)
                         ~~^~~~~~~~~~~~
password.cpp:32:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = l2; i < b.length(); i++)
                         ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Guessed the password with 60 queries.
2 Correct 6 ms 248 KB Guessed the password with 100 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Guessed the password with 48 queries.
2 Correct 6 ms 376 KB Guessed the password with 89 queries.
3 Correct 6 ms 376 KB Guessed the password with 91 queries.
4 Correct 8 ms 252 KB Guessed the password with 200 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 324 KB Guessed the password with 3553 queries.
2 Correct 62 ms 248 KB Guessed the password with 5017 queries.
3 Correct 67 ms 376 KB Guessed the password with 6347 queries.
4 Correct 88 ms 376 KB Guessed the password with 8584 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Guessed the password with 60 queries.
2 Correct 6 ms 248 KB Guessed the password with 100 queries.
3 Correct 5 ms 248 KB Guessed the password with 48 queries.
4 Correct 6 ms 376 KB Guessed the password with 89 queries.
5 Correct 6 ms 376 KB Guessed the password with 91 queries.
6 Correct 8 ms 252 KB Guessed the password with 200 queries.
7 Correct 41 ms 324 KB Guessed the password with 3553 queries.
8 Correct 62 ms 248 KB Guessed the password with 5017 queries.
9 Correct 67 ms 376 KB Guessed the password with 6347 queries.
10 Correct 88 ms 376 KB Guessed the password with 8584 queries.
11 Correct 134 ms 456 KB Guessed the password with 12821 queries.
12 Correct 150 ms 504 KB Guessed the password with 12723 queries.
13 Correct 158 ms 376 KB Guessed the password with 13986 queries.
14 Correct 155 ms 504 KB Guessed the password with 13990 queries.
15 Correct 163 ms 632 KB Guessed the password with 14699 queries.
16 Correct 168 ms 332 KB Guessed the password with 14712 queries.
17 Correct 161 ms 460 KB Guessed the password with 15036 queries.
18 Correct 171 ms 376 KB Guessed the password with 15134 queries.
19 Correct 178 ms 376 KB Guessed the password with 15349 queries.
20 Correct 159 ms 504 KB Guessed the password with 14369 queries.
21 Correct 183 ms 560 KB Guessed the password with 16168 queries.
22 Correct 174 ms 508 KB Guessed the password with 15433 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Guessed the password with 60 queries.
2 Correct 6 ms 248 KB Guessed the password with 100 queries.
3 Correct 5 ms 248 KB Guessed the password with 48 queries.
4 Correct 6 ms 376 KB Guessed the password with 89 queries.
5 Correct 6 ms 376 KB Guessed the password with 91 queries.
6 Correct 8 ms 252 KB Guessed the password with 200 queries.
7 Correct 41 ms 324 KB Guessed the password with 3553 queries.
8 Correct 62 ms 248 KB Guessed the password with 5017 queries.
9 Correct 67 ms 376 KB Guessed the password with 6347 queries.
10 Correct 88 ms 376 KB Guessed the password with 8584 queries.
11 Correct 134 ms 456 KB Guessed the password with 12821 queries.
12 Correct 150 ms 504 KB Guessed the password with 12723 queries.
13 Correct 158 ms 376 KB Guessed the password with 13986 queries.
14 Correct 155 ms 504 KB Guessed the password with 13990 queries.
15 Correct 163 ms 632 KB Guessed the password with 14699 queries.
16 Correct 168 ms 332 KB Guessed the password with 14712 queries.
17 Correct 161 ms 460 KB Guessed the password with 15036 queries.
18 Correct 171 ms 376 KB Guessed the password with 15134 queries.
19 Correct 178 ms 376 KB Guessed the password with 15349 queries.
20 Correct 159 ms 504 KB Guessed the password with 14369 queries.
21 Correct 183 ms 560 KB Guessed the password with 16168 queries.
22 Correct 174 ms 508 KB Guessed the password with 15433 queries.
23 Correct 277 ms 584 KB Guessed the password with 23768 queries.
24 Correct 299 ms 452 KB Guessed the password with 23340 queries.
25 Correct 267 ms 672 KB Guessed the password with 23723 queries.
26 Correct 282 ms 556 KB Guessed the password with 23269 queries.
27 Correct 267 ms 444 KB Guessed the password with 23779 queries.
28 Correct 281 ms 584 KB Guessed the password with 23058 queries.
29 Correct 239 ms 688 KB Guessed the password with 23782 queries.
30 Correct 271 ms 544 KB Guessed the password with 22572 queries.