oj.uz

Submission #755926

# Submission time Handle Problem Language Result Execution time Memory
755926 2023-06-10T17:48:43 Z vjudge1 Password (RMI18_password) C++17
80 / 100
 737 ms 608 KB 
#include<bits/stdc++.h>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree<pair<int, int>, null_type, less<pair<int, int>>,rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
int dx[8] = {1, 0, 0, -1, 1, 1, -1, -1};
int dy[8] = {0, 1, -1, 0, 1, -1, -1, 1};
#define endl "\n"
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
////////////////////Only Clear Code//////////////////////////

void init(){
    #ifndef ONLINE_JUDGE
 
freopen("input.txt", "r", stdin);
 
freopen("output.txt", "w", stdout);
 
#endif // ONLINE_JUDGE
}

const int mx = 1e6+9;
const int LOG = 25;
const ll inf = 1e18;
const ll mod = 1e9+7;

int freq[30];

string pass;
bool subsequence(string a, string b){
    int ind = 0;
    for(int i = 0; i < b.size();i++){
        if(b[i] == a[ind]){
            ind++;
            if(ind == a.size())return 1;
        }
    }
    return 0;
}

int query(string str);

string guess(int n, int s){
    for(int i = 0; i < s;i++){
        freq[i] = 0;
    }
    for(int i = 0; i < s;i++){
        char x = i+'a';
        string c = string(1, x);
        while(c.size() <= n){
            int res = query(c);
            if(res == c.size())freq[i] = c.size();
            else break;
            c += x;
        }
    }
    string c = "";
    for(int i = 0; i < s;i++){
        char x = i+'a';
        if(freq[i] != 0){
            int k = freq[i];
            while(k--){
                c += x;
            }
            freq[i] = 0;
            break;
        }
    }
    for(int j = 0; j < s;j++){
        if(freq[j] == 0)continue;
        string x = string(1, char(j + 'a'));
        string temp = "";
        vi v;
        while(freq[j]--){
            temp += x;
            int l = 0, r = c.size();
            int ind = c.size();
            while(l <= r){
                int md = (l+r)/2;
                string mat = "";
                for(int i = 0; i < md;i++){
                    mat += c[i];
                }
                string one = mat + temp;
                if(query(one) == one.size()){
                    ind = md;
                    l = md+1;
                }
                else{
                    r = md-1;
                }
            }
            v.pb(ind-1);
        }
        //cout << x << " "  << c << endl;
        int cnt = 0;
        sort(all(v));
        for(int y : v){
            //cout << y << " ";
            c.insert(y+cnt+1,x);
            cnt++;
        }
        //cout << endl;
    }
    return c;
}

/*string guess(int n, int s){
    string c = "";
    for(int i = 0; i < s;i++){
        char x = i + 'a';
        if(query(c + x) != 0){
            c = x;
            break;
        }
    }
    for(int i = 0;c.size() < n && i < s;i++){
        char x = i + 'a';
        //cout << x << endl;
        while(c.size() < n){
            bool ok = 0;
            for(int j = 0;j <= c.size();j++){
                string temp = c;
                temp.insert(j, string(1, x));
                if(query(temp) == temp.size()){
                    c = temp;
                    ok = 1;
                    break;
                    
                }
            }
            if(!ok){
                break;
            }
        }
    }
    return c;
}*/
/*
void run_case(){
    pass = "aeafeddbadcab";
    string s = guess(13, 6);
    cout << s << endl;
    cout << (s == pass ? "YES" : "NO") << endl;
}

int main(){
    init();
    speed;
    int t;
    //cin >> t;
    t = 1;
    while(t--){
        run_case();
    }
}*/

/*
    NEVER GIVE UP!
    DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
    Your Guide when stuck:
    - Continue keyword only after reading the whole input
    - Don't use memset with testcases
    - Check for corner cases(n=1, n=0)
    - Check where you declare n(Be careful of declaring it globally and in main)
*/

Compilation message

password.cpp: In function 'bool subsequence(std::string, std::string)':
password.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 0; i < b.size();i++){
      |                    ~~^~~~~~~~~~
password.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             if(ind == a.size())return 1;
      |                ~~~~^~~~~~~~~~~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:70:24: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |         while(c.size() <= n){
      |               ~~~~~~~~~^~~~
password.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             if(res == c.size())freq[i] = c.size();
      |                ~~~~^~~~~~~~~~~
password.cpp:105:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |                 if(query(one) == one.size()){
      |                    ~~~~~~~~~~~^~~~~~~~~~~~~
password.cpp: In function 'void init()':
password.cpp:35:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
password.cpp:37:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 75 queries.
2 Correct 2 ms 208 KB Guessed the password with 124 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 174 queries.
2 Correct 2 ms 208 KB Guessed the password with 205 queries.
3 Correct 4 ms 208 KB Guessed the password with 414 queries.
4 Correct 9 ms 208 KB Guessed the password with 559 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 328 KB Guessed the password with 8953 queries.
2 Correct 102 ms 416 KB Guessed the password with 12373 queries.
3 Correct 95 ms 300 KB Guessed the password with 15322 queries.
4 Correct 214 ms 412 KB Guessed the password with 20474 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 75 queries.
2 Correct 2 ms 208 KB Guessed the password with 124 queries.
3 Correct 2 ms 208 KB Guessed the password with 174 queries.
4 Correct 2 ms 208 KB Guessed the password with 205 queries.
5 Correct 4 ms 208 KB Guessed the password with 414 queries.
6 Correct 9 ms 208 KB Guessed the password with 559 queries.
7 Correct 83 ms 328 KB Guessed the password with 8953 queries.
8 Correct 102 ms 416 KB Guessed the password with 12373 queries.
9 Correct 95 ms 300 KB Guessed the password with 15322 queries.
10 Correct 214 ms 412 KB Guessed the password with 20474 queries.
11 Correct 332 ms 444 KB Guessed the password with 25501 queries.
12 Correct 391 ms 364 KB Guessed the password with 30033 queries.
13 Correct 363 ms 556 KB Guessed the password with 30533 queries.
14 Correct 383 ms 424 KB Guessed the password with 32630 queries.
15 Correct 477 ms 592 KB Guessed the password with 31655 queries.
16 Correct 455 ms 324 KB Guessed the password with 34923 queries.
17 Correct 460 ms 484 KB Guessed the password with 31578 queries.
18 Correct 447 ms 484 KB Guessed the password with 36216 queries.
19 Correct 468 ms 608 KB Guessed the password with 31168 queries.
20 Correct 482 ms 424 KB Guessed the password with 37303 queries.
21 Correct 480 ms 476 KB Guessed the password with 34747 queries.
22 Correct 392 ms 412 KB Guessed the password with 39069 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 75 queries.
2 Correct 2 ms 208 KB Guessed the password with 124 queries.
3 Correct 2 ms 208 KB Guessed the password with 174 queries.
4 Correct 2 ms 208 KB Guessed the password with 205 queries.
5 Correct 4 ms 208 KB Guessed the password with 414 queries.
6 Correct 9 ms 208 KB Guessed the password with 559 queries.
7 Correct 83 ms 328 KB Guessed the password with 8953 queries.
8 Correct 102 ms 416 KB Guessed the password with 12373 queries.
9 Correct 95 ms 300 KB Guessed the password with 15322 queries.
10 Correct 214 ms 412 KB Guessed the password with 20474 queries.
11 Correct 332 ms 444 KB Guessed the password with 25501 queries.
12 Correct 391 ms 364 KB Guessed the password with 30033 queries.
13 Correct 363 ms 556 KB Guessed the password with 30533 queries.
14 Correct 383 ms 424 KB Guessed the password with 32630 queries.
15 Correct 477 ms 592 KB Guessed the password with 31655 queries.
16 Correct 455 ms 324 KB Guessed the password with 34923 queries.
17 Correct 460 ms 484 KB Guessed the password with 31578 queries.
18 Correct 447 ms 484 KB Guessed the password with 36216 queries.
19 Correct 468 ms 608 KB Guessed the password with 31168 queries.
20 Correct 482 ms 424 KB Guessed the password with 37303 queries.
21 Correct 480 ms 476 KB Guessed the password with 34747 queries.
22 Correct 392 ms 412 KB Guessed the password with 39069 queries.
23 Incorrect 737 ms 432 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -