oj.uz

Submission #201145

# Submission time Handle Problem Language Result Execution time Memory
201145 2020-02-09T12:27:04 Z Atill83 Password (RMI18_password) C++14
50 / 100
 3000 ms 636 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string str);

int freq[30];

string solve(int l, int r){
    if(l == r){
        string a;
        for(int i = 0; i < freq[l]; i++) a += (char)('a' + l);
        return a;
    }
    int m = (l + r) / 2;
    string a = solve(l, m), b = solve(m + 1, r);

    string ans;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    while(a.length() && b.length()){
        string soru = ans + a.back();
        for(auto i = b.rbegin(); i < b.rend(); i++) soru = soru + (*i);
        int quer = query(soru);
        if(quer == soru.length()){
            ans += a.back();
            a.pop_back();
        }else{
            ans += b.back();
            b.pop_back();
        }
    }
    while(a.length()){
        ans += a.back();
        a.pop_back();
    }
    while(b.length()){
        ans += b.back();
        b.pop_back();
    }

    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] = query(que);
        sum += freq[i];
    }
    freq[s - 1] = n - sum;
    return solve(0, s - 1);
}

Compilation message

password.cpp: In function 'std::__cxx11::string solve(int, int)':
password.cpp:24:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(quer == soru.length()){
            ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 376 KB Guessed the password with 48 queries.
2 Correct 6 ms 248 KB Guessed the password with 116 queries.
3 Correct 8 ms 248 KB Guessed the password with 91 queries.
4 Correct 8 ms 376 KB Guessed the password with 196 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 376 KB Guessed the password with 3455 queries.
2 Correct 271 ms 408 KB Guessed the password with 5024 queries.
3 Correct 466 ms 504 KB Guessed the password with 6351 queries.
4 Correct 785 ms 376 KB Guessed the password with 8692 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 376 KB Guessed the password with 48 queries.
4 Correct 6 ms 248 KB Guessed the password with 116 queries.
5 Correct 8 ms 248 KB Guessed the password with 91 queries.
6 Correct 8 ms 376 KB Guessed the password with 196 queries.
7 Correct 209 ms 376 KB Guessed the password with 3455 queries.
8 Correct 271 ms 408 KB Guessed the password with 5024 queries.
9 Correct 466 ms 504 KB Guessed the password with 6351 queries.
10 Correct 785 ms 376 KB Guessed the password with 8692 queries.
11 Correct 1012 ms 636 KB Guessed the password with 13637 queries.
12 Execution timed out 3057 ms 248 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 376 KB Guessed the password with 48 queries.
4 Correct 6 ms 248 KB Guessed the password with 116 queries.
5 Correct 8 ms 248 KB Guessed the password with 91 queries.
6 Correct 8 ms 376 KB Guessed the password with 196 queries.
7 Correct 209 ms 376 KB Guessed the password with 3455 queries.
8 Correct 271 ms 408 KB Guessed the password with 5024 queries.
9 Correct 466 ms 504 KB Guessed the password with 6351 queries.
10 Correct 785 ms 376 KB Guessed the password with 8692 queries.
11 Correct 1012 ms 636 KB Guessed the password with 13637 queries.
12 Execution timed out 3057 ms 248 KB Time limit exceeded
13 Halted 0 ms 0 KB -