oj.uz

Submission #755929

# Submission time Handle Problem Language Result Execution time Memory
755929 2023-06-10T17:51:24 Z vjudge1 Password (RMI18_password) C++17
80 / 100
 757 ms 708 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 = (v.empty() ? c.size() : v.back()+1);
            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 129 queries.
2 Correct 2 ms 208 KB Guessed the password with 180 queries.
3 Correct 2 ms 208 KB Guessed the password with 183 queries.
4 Correct 5 ms 208 KB Guessed the password with 492 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 300 KB Guessed the password with 7750 queries.
2 Correct 117 ms 324 KB Guessed the password with 10372 queries.
3 Correct 169 ms 420 KB Guessed the password with 13548 queries.
4 Correct 178 ms 448 KB Guessed the password with 18732 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 129 queries.
4 Correct 2 ms 208 KB Guessed the password with 180 queries.
5 Correct 2 ms 208 KB Guessed the password with 183 queries.
6 Correct 5 ms 208 KB Guessed the password with 492 queries.
7 Correct 87 ms 300 KB Guessed the password with 7750 queries.
8 Correct 117 ms 324 KB Guessed the password with 10372 queries.
9 Correct 169 ms 420 KB Guessed the password with 13548 queries.
10 Correct 178 ms 448 KB Guessed the password with 18732 queries.
11 Correct 255 ms 340 KB Guessed the password with 22960 queries.
12 Correct 349 ms 464 KB Guessed the password with 26808 queries.
13 Correct 248 ms 348 KB Guessed the password with 27457 queries.
14 Correct 358 ms 428 KB Guessed the password with 29507 queries.
15 Correct 401 ms 456 KB Guessed the password with 28201 queries.
16 Correct 377 ms 680 KB Guessed the password with 31010 queries.
17 Correct 339 ms 468 KB Guessed the password with 27411 queries.
18 Correct 421 ms 468 KB Guessed the password with 32611 queries.
19 Correct 391 ms 708 KB Guessed the password with 27948 queries.
20 Correct 441 ms 456 KB Guessed the password with 33592 queries.
21 Correct 408 ms 360 KB Guessed the password with 30393 queries.
22 Correct 321 ms 460 KB Guessed the password with 32980 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 129 queries.
4 Correct 2 ms 208 KB Guessed the password with 180 queries.
5 Correct 2 ms 208 KB Guessed the password with 183 queries.
6 Correct 5 ms 208 KB Guessed the password with 492 queries.
7 Correct 87 ms 300 KB Guessed the password with 7750 queries.
8 Correct 117 ms 324 KB Guessed the password with 10372 queries.
9 Correct 169 ms 420 KB Guessed the password with 13548 queries.
10 Correct 178 ms 448 KB Guessed the password with 18732 queries.
11 Correct 255 ms 340 KB Guessed the password with 22960 queries.
12 Correct 349 ms 464 KB Guessed the password with 26808 queries.
13 Correct 248 ms 348 KB Guessed the password with 27457 queries.
14 Correct 358 ms 428 KB Guessed the password with 29507 queries.
15 Correct 401 ms 456 KB Guessed the password with 28201 queries.
16 Correct 377 ms 680 KB Guessed the password with 31010 queries.
17 Correct 339 ms 468 KB Guessed the password with 27411 queries.
18 Correct 421 ms 468 KB Guessed the password with 32611 queries.
19 Correct 391 ms 708 KB Guessed the password with 27948 queries.
20 Correct 441 ms 456 KB Guessed the password with 33592 queries.
21 Correct 408 ms 360 KB Guessed the password with 30393 queries.
22 Correct 321 ms 460 KB Guessed the password with 32980 queries.
23 Incorrect 757 ms 472 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -