oj.uz

Submission #199700

# Submission time Handle Problem Language Result Execution time Memory
199700 2020-02-02T22:54:46 Z mohamedsobhi777 Password (RMI18_password) C++17
100 / 100
 361 ms 784 KB 
#include <bits/stdc++.h>
using namespace std;

int N = 2000;
vector<int> acc(26 , 0);
int query(string s);

string merg(string aa , string bb)
{
    int s1 = aa.size();
    int s2 = bb.size();
    string ret = aa;
    int j = s2-1;
    for(int i = s1;i>=0&&j>=0;i--)
    {
        string tmp ;
        bool ok = 1;
        while(ok && j>=0)
        {
            tmp = ret.substr(0 , i) + bb[j];
            tmp+=ret.substr( i , s1 - i );
            if(query(tmp)==tmp.size())
            {
                ret = tmp;
                s1++;
                j--;
            }else ok = 0;
        }
    }
    return ret ;
}
int l[550] , r[550];

string build(int i)
{
    if(l[i] ==r[i] && r[i] ==-1 )
        return string( acc[i] , char('a' + i));
    string s1 = "";
    string s2 = "";
    if(l[i]!=-1)
        s1 = build(l[i] );
    if(r[i]!=-1)
        s2 = build(r[i] );
    string ret = merg(s1 , s2);
    return ret;

}
int t = 1;

string guess(int n, int s)
{
    memset(l , -1 , sizeof l);
    memset(r , -1 , sizeof r);
    int sum = 0;
    for(int i = 'a';i<'a' + s -1 ;i++)
    {
        acc[i-'a'] = query(string(n , char(i)));
        sum+=acc[i-'a'];
    }
    acc[s - 1] =  n  - sum;
    //hUFFMAN CODING
    priority_queue<pair<int , int> > q;

    for(int i= 0;i<s;i++)
        if(acc[i])
            q.push({ -acc[i] , i });
    t = s+1;
    while(q.size() > 1)
    {
        pair<int ,int > tp1 = q.top();q.pop();
        pair<int ,int > tp2 = q.top();q.pop();
        int sum = tp1.first+tp2.first;
        l[t] = tp1.second;
        r[t] = tp2.second;
        q.push({sum , t++});
    }
    return build(q.top().second);
}

Compilation message

password.cpp: In function 'std::__cxx11::string merg(std::__cxx11::string, std::__cxx11::string)':
password.cpp:22:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(query(tmp)==tmp.size())
                ~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Guessed the password with 51 queries.
2 Correct 6 ms 248 KB Guessed the password with 94 queries.
3 Correct 6 ms 248 KB Guessed the password with 104 queries.
4 Correct 6 ms 328 KB Guessed the password with 179 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 376 KB Guessed the password with 2770 queries.
2 Correct 55 ms 332 KB Guessed the password with 5092 queries.
3 Correct 54 ms 376 KB Guessed the password with 4599 queries.
4 Correct 102 ms 376 KB Guessed the password with 8150 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Guessed the password with 66 queries.
2 Correct 6 ms 248 KB Guessed the password with 115 queries.
3 Correct 6 ms 376 KB Guessed the password with 51 queries.
4 Correct 6 ms 248 KB Guessed the password with 94 queries.
5 Correct 6 ms 248 KB Guessed the password with 104 queries.
6 Correct 6 ms 328 KB Guessed the password with 179 queries.
7 Correct 45 ms 376 KB Guessed the password with 2770 queries.
8 Correct 55 ms 332 KB Guessed the password with 5092 queries.
9 Correct 54 ms 376 KB Guessed the password with 4599 queries.
10 Correct 102 ms 376 KB Guessed the password with 8150 queries.
11 Correct 134 ms 508 KB Guessed the password with 8181 queries.
12 Correct 84 ms 376 KB Guessed the password with 8178 queries.
13 Correct 112 ms 504 KB Guessed the password with 11550 queries.
14 Correct 155 ms 376 KB Guessed the password with 11684 queries.
15 Correct 108 ms 452 KB Guessed the password with 10907 queries.
16 Correct 111 ms 632 KB Guessed the password with 10882 queries.
17 Correct 82 ms 424 KB Guessed the password with 10239 queries.
18 Correct 121 ms 428 KB Guessed the password with 10303 queries.
19 Correct 154 ms 376 KB Guessed the password with 9708 queries.
20 Correct 110 ms 556 KB Guessed the password with 9806 queries.
21 Correct 135 ms 248 KB Guessed the password with 11733 queries.
22 Correct 97 ms 324 KB Guessed the password with 11814 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Guessed the password with 66 queries.
2 Correct 6 ms 248 KB Guessed the password with 115 queries.
3 Correct 6 ms 376 KB Guessed the password with 51 queries.
4 Correct 6 ms 248 KB Guessed the password with 94 queries.
5 Correct 6 ms 248 KB Guessed the password with 104 queries.
6 Correct 6 ms 328 KB Guessed the password with 179 queries.
7 Correct 45 ms 376 KB Guessed the password with 2770 queries.
8 Correct 55 ms 332 KB Guessed the password with 5092 queries.
9 Correct 54 ms 376 KB Guessed the password with 4599 queries.
10 Correct 102 ms 376 KB Guessed the password with 8150 queries.
11 Correct 134 ms 508 KB Guessed the password with 8181 queries.
12 Correct 84 ms 376 KB Guessed the password with 8178 queries.
13 Correct 112 ms 504 KB Guessed the password with 11550 queries.
14 Correct 155 ms 376 KB Guessed the password with 11684 queries.
15 Correct 108 ms 452 KB Guessed the password with 10907 queries.
16 Correct 111 ms 632 KB Guessed the password with 10882 queries.
17 Correct 82 ms 424 KB Guessed the password with 10239 queries.
18 Correct 121 ms 428 KB Guessed the password with 10303 queries.
19 Correct 154 ms 376 KB Guessed the password with 9708 queries.
20 Correct 110 ms 556 KB Guessed the password with 9806 queries.
21 Correct 135 ms 248 KB Guessed the password with 11733 queries.
22 Correct 97 ms 324 KB Guessed the password with 11814 queries.
23 Correct 302 ms 484 KB Guessed the password with 23739 queries.
24 Correct 317 ms 596 KB Guessed the password with 20993 queries.
25 Correct 297 ms 532 KB Guessed the password with 23736 queries.
26 Correct 276 ms 444 KB Guessed the password with 19153 queries.
27 Correct 361 ms 540 KB Guessed the password with 23755 queries.
28 Correct 260 ms 784 KB Guessed the password with 16845 queries.
29 Correct 304 ms 688 KB Guessed the password with 23724 queries.
30 Correct 204 ms 656 KB Guessed the password with 14412 queries.