oj.uz

Submission #199698

# Submission time Handle Problem Language Result Execution time Memory
199698 2020-02-02T20:47:43 Z mohamedsobhi777 Password (RMI18_password) C++14
100 / 100
 360 ms 864 KB 
#include <bits/stdc++.h>
using namespace std;

string a[1000];

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 ;
}

string build(int l, int r )
{

    if(l==r)
    {
        return string( acc[l] , char(l + 'a'));
    }
    else
    {
        int mid = (l + r) /2;
        string s1 = build(l , mid );
        string s2 = build(mid+1 , r);
        string ret = merg(s1 , s2);
        return ret;
    }
}



string guess(int n, int s)
{
    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;
    return build(0 , s-1);
}

Compilation message

password.cpp: In function 'std::__cxx11::string merg(std::__cxx11::string, std::__cxx11::string)':
password.cpp:25: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 5 ms 376 KB Guessed the password with 66 queries.
2 Correct 7 ms 376 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 248 KB Guessed the password with 51 queries.
2 Correct 7 ms 248 KB Guessed the password with 121 queries.
3 Correct 6 ms 248 KB Guessed the password with 94 queries.
4 Correct 8 ms 248 KB Guessed the password with 202 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 248 KB Guessed the password with 3710 queries.
2 Correct 62 ms 248 KB Guessed the password with 5112 queries.
3 Correct 88 ms 360 KB Guessed the password with 6615 queries.
4 Correct 97 ms 248 KB Guessed the password with 8761 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Guessed the password with 66 queries.
2 Correct 7 ms 376 KB Guessed the password with 111 queries.
3 Correct 6 ms 248 KB Guessed the password with 51 queries.
4 Correct 7 ms 248 KB Guessed the password with 121 queries.
5 Correct 6 ms 248 KB Guessed the password with 94 queries.
6 Correct 8 ms 248 KB Guessed the password with 202 queries.
7 Correct 46 ms 248 KB Guessed the password with 3710 queries.
8 Correct 62 ms 248 KB Guessed the password with 5112 queries.
9 Correct 88 ms 360 KB Guessed the password with 6615 queries.
10 Correct 97 ms 248 KB Guessed the password with 8761 queries.
11 Correct 194 ms 376 KB Guessed the password with 12872 queries.
12 Correct 177 ms 556 KB Guessed the password with 12752 queries.
13 Correct 210 ms 376 KB Guessed the password with 14238 queries.
14 Correct 188 ms 504 KB Guessed the password with 13911 queries.
15 Correct 212 ms 376 KB Guessed the password with 15078 queries.
16 Correct 196 ms 376 KB Guessed the password with 14791 queries.
17 Correct 223 ms 376 KB Guessed the password with 16128 queries.
18 Correct 212 ms 636 KB Guessed the password with 15066 queries.
19 Correct 208 ms 376 KB Guessed the password with 16416 queries.
20 Correct 232 ms 632 KB Guessed the password with 15410 queries.
21 Correct 200 ms 484 KB Guessed the password with 16766 queries.
22 Correct 156 ms 376 KB Guessed the password with 16216 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Guessed the password with 66 queries.
2 Correct 7 ms 376 KB Guessed the password with 111 queries.
3 Correct 6 ms 248 KB Guessed the password with 51 queries.
4 Correct 7 ms 248 KB Guessed the password with 121 queries.
5 Correct 6 ms 248 KB Guessed the password with 94 queries.
6 Correct 8 ms 248 KB Guessed the password with 202 queries.
7 Correct 46 ms 248 KB Guessed the password with 3710 queries.
8 Correct 62 ms 248 KB Guessed the password with 5112 queries.
9 Correct 88 ms 360 KB Guessed the password with 6615 queries.
10 Correct 97 ms 248 KB Guessed the password with 8761 queries.
11 Correct 194 ms 376 KB Guessed the password with 12872 queries.
12 Correct 177 ms 556 KB Guessed the password with 12752 queries.
13 Correct 210 ms 376 KB Guessed the password with 14238 queries.
14 Correct 188 ms 504 KB Guessed the password with 13911 queries.
15 Correct 212 ms 376 KB Guessed the password with 15078 queries.
16 Correct 196 ms 376 KB Guessed the password with 14791 queries.
17 Correct 223 ms 376 KB Guessed the password with 16128 queries.
18 Correct 212 ms 636 KB Guessed the password with 15066 queries.
19 Correct 208 ms 376 KB Guessed the password with 16416 queries.
20 Correct 232 ms 632 KB Guessed the password with 15410 queries.
21 Correct 200 ms 484 KB Guessed the password with 16766 queries.
22 Correct 156 ms 376 KB Guessed the password with 16216 queries.
23 Correct 259 ms 484 KB Guessed the password with 23778 queries.
24 Correct 286 ms 504 KB Guessed the password with 23121 queries.
25 Correct 317 ms 720 KB Guessed the password with 23843 queries.
26 Correct 317 ms 684 KB Guessed the password with 23164 queries.
27 Correct 360 ms 864 KB Guessed the password with 23798 queries.
28 Correct 293 ms 556 KB Guessed the password with 23909 queries.
29 Correct 349 ms 688 KB Guessed the password with 23856 queries.
30 Correct 322 ms 540 KB Guessed the password with 22868 queries.