oj.uz

Submission #251360

# Submission time Handle Problem Language Result Execution time Memory
251360 2020-07-21T02:24:34 Z dantoh000 Password (RMI18_password) C++14
100 / 100
 557 ms 776 KB 
#include <bits/stdc++.h>
using namespace std;
int ct[26];
int query(string str);
vector<char> Q;
vector<char> T;
vector<string> pq;
bool query(){
    string str = "";
    for (auto x : Q) str += x;
    for (int i = T.size()-1; i >= 0; i--) str += T[i];
    return query(str) == str.size();
}
string merge(string s, string t){
    Q.clear();
    string test = ""; test += s[0];
    for (auto x : t) test += x;
    if (s.size() == 0 || query(test) != t.size()+1){
        swap(s,t);
    }
    int n = s.size(), m = t.size();
    int cur = 0;
    for (int i = n-1; i >= 0; i--){
        T.push_back(s[i]);
    }
    for (int i = 0; i < n-1; i++){
        Q.push_back(s[i]);
        T.pop_back();
        //printf("before adding s %c\n",s[i]);
        while (cur < m){
            Q.push_back(t[cur]);
            if (query()) {
                //printf("adding t %c\n",t[cur]);
                cur++;
            }
            else {
                Q.pop_back();
                break;
            }
        }
    }
    Q.push_back(s[n-1]);
    T.pop_back();
    while (cur < m){
        Q.push_back(t[cur++]);
    }

    string ans= "";
    for (auto x : Q) ans += x;
    //cout << "merged " << s  << " and " << t << ", " << ans << endl;
    return ans;
}
bool cmp(string a, string b){
    return a.size() > b.size();
}
string guess(int n, int s){
    string q = "";
    int sum = 0;
    for (int i = 0; i < s-1; i++){
        q = "";
        for (ct[i] = 1; ct[i] <= n; ct[i]++){
            q += (i+'a');
            if (query(q) != ct[i]) {
                ct[i]--;
                break;
            }
        }
        sum+=ct[i];
    }
    ct[s-1] = n-sum;
    for (int i =0; i < s; i++){
        pq.push_back(string(ct[i],(char)(i+'a')));
        //printf("%d ",ct[i]);
    }
    sort(pq.begin(),pq.end(),cmp);
    while (pq.size() != 1){
        string s = pq.back(); pq.pop_back();
        string t = pq.back(); pq.pop_back();
        pq.push_back(merge(s,t));
        sort(pq.begin(),pq.end(),cmp);
    }
    return pq[0];
}

Compilation message

password.cpp: In function 'bool query()':
password.cpp:12:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return query(str) == str.size();
            ~~~~~~~~~~~^~~~~~~~~~~~~
password.cpp: In function 'std::__cxx11::string merge(std::__cxx11::string, std::__cxx11::string)':
password.cpp:18:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (s.size() == 0 || query(test) != t.size()+1){
                          ~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 69 queries.
2 Correct 2 ms 256 KB Guessed the password with 126 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 72 queries.
2 Correct 2 ms 256 KB Guessed the password with 143 queries.
3 Correct 1 ms 256 KB Guessed the password with 103 queries.
4 Correct 3 ms 256 KB Guessed the password with 244 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 376 KB Guessed the password with 3585 queries.
2 Correct 82 ms 368 KB Guessed the password with 6289 queries.
3 Correct 84 ms 376 KB Guessed the password with 6137 queries.
4 Correct 134 ms 376 KB Guessed the password with 9917 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 69 queries.
2 Correct 2 ms 256 KB Guessed the password with 126 queries.
3 Correct 1 ms 256 KB Guessed the password with 72 queries.
4 Correct 2 ms 256 KB Guessed the password with 143 queries.
5 Correct 1 ms 256 KB Guessed the password with 103 queries.
6 Correct 3 ms 256 KB Guessed the password with 244 queries.
7 Correct 41 ms 376 KB Guessed the password with 3585 queries.
8 Correct 82 ms 368 KB Guessed the password with 6289 queries.
9 Correct 84 ms 376 KB Guessed the password with 6137 queries.
10 Correct 134 ms 376 KB Guessed the password with 9917 queries.
11 Correct 167 ms 376 KB Guessed the password with 10867 queries.
12 Correct 155 ms 504 KB Guessed the password with 10317 queries.
13 Correct 192 ms 512 KB Guessed the password with 14448 queries.
14 Correct 204 ms 516 KB Guessed the password with 14232 queries.
15 Correct 236 ms 376 KB Guessed the password with 14080 queries.
16 Correct 214 ms 504 KB Guessed the password with 13547 queries.
17 Correct 232 ms 396 KB Guessed the password with 13507 queries.
18 Correct 220 ms 504 KB Guessed the password with 12914 queries.
19 Correct 213 ms 512 KB Guessed the password with 13081 queries.
20 Correct 211 ms 384 KB Guessed the password with 12377 queries.
21 Correct 233 ms 636 KB Guessed the password with 15039 queries.
22 Correct 243 ms 504 KB Guessed the password with 14613 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 69 queries.
2 Correct 2 ms 256 KB Guessed the password with 126 queries.
3 Correct 1 ms 256 KB Guessed the password with 72 queries.
4 Correct 2 ms 256 KB Guessed the password with 143 queries.
5 Correct 1 ms 256 KB Guessed the password with 103 queries.
6 Correct 3 ms 256 KB Guessed the password with 244 queries.
7 Correct 41 ms 376 KB Guessed the password with 3585 queries.
8 Correct 82 ms 368 KB Guessed the password with 6289 queries.
9 Correct 84 ms 376 KB Guessed the password with 6137 queries.
10 Correct 134 ms 376 KB Guessed the password with 9917 queries.
11 Correct 167 ms 376 KB Guessed the password with 10867 queries.
12 Correct 155 ms 504 KB Guessed the password with 10317 queries.
13 Correct 192 ms 512 KB Guessed the password with 14448 queries.
14 Correct 204 ms 516 KB Guessed the password with 14232 queries.
15 Correct 236 ms 376 KB Guessed the password with 14080 queries.
16 Correct 214 ms 504 KB Guessed the password with 13547 queries.
17 Correct 232 ms 396 KB Guessed the password with 13507 queries.
18 Correct 220 ms 504 KB Guessed the password with 12914 queries.
19 Correct 213 ms 512 KB Guessed the password with 13081 queries.
20 Correct 211 ms 384 KB Guessed the password with 12377 queries.
21 Correct 233 ms 636 KB Guessed the password with 15039 queries.
22 Correct 243 ms 504 KB Guessed the password with 14613 queries.
23 Correct 503 ms 632 KB Guessed the password with 28424 queries.
24 Correct 512 ms 568 KB Guessed the password with 25539 queries.
25 Correct 533 ms 760 KB Guessed the password with 28475 queries.
26 Correct 436 ms 776 KB Guessed the password with 24090 queries.
27 Correct 557 ms 636 KB Guessed the password with 28498 queries.
28 Correct 398 ms 660 KB Guessed the password with 21816 queries.
29 Correct 525 ms 764 KB Guessed the password with 28514 queries.
30 Correct 395 ms 744 KB Guessed the password with 19357 queries.