oj.uz

Submission #433747

# Submission time Handle Problem Language Result Execution time Memory
433747 2021-06-20T10:16:06 Z AmineWeslati Password (RMI18_password) C++14
80 / 100
 1162 ms 568 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)

typedef string str; 

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)


void ckmin(int &x, int y){x=min(x,y);}
//------------------------------------

int query(string S);

int alp;

void upd(str &s, int idx, char c){
    str ss;
    FOR(i,0,sz(s)+1){
        if(i==idx) ss+=c;
        if(i<sz(s)) ss+=s[i];
    }
    s=ss; 
}

bool check(str s, int idx, char c){
    str ss; 
    FOR(i,0,idx) ss+=s[i];
    ss+=c; 

    int x=sz(ss);

    FOR(i,idx,sz(s)) if(s[i]==c) ss+=s[i];

    return query(ss)==sz(ss);
}

str guess(int N, int S){
    alp=S; 
    vi nb(alp);
    for(char c='a'; c<=char('a'+alp-1); c++){
        str s;
        FOR(i,0,N) s+=c; 
        nb[c-'a']=query(s);
    }

     
    int idx=0;
    FOR(i,0,alp) if(nb[i]>nb[idx]) idx=i; 

    idx=0;

    str cur;
    FOR(i,0,nb[idx]) cur+=char(idx+'a');

    FOR(i,0,alp) if(i!=idx){
        char c=i+'a';
        while(nb[i]--){
            int l=0,r=sz(cur),ind=-1;
            while(l<=r){
                int m=(l+r)/2;
                if(check(cur,m,c)){
                    ind=m; 
                    l=m+1;
                }
                else r=m-1;
            }
            //if(ind==-1) cout << "here" << endl;

            upd(cur,ind,c);

            //cout << cur << endl;
        }
    }
    //cout << sz(cur) << endl;
    return cur; 
}

Compilation message

password.cpp: In function 'bool check(str, int, char)':
password.cpp:37:9: warning: unused variable 'x' [-Wunused-variable]
   37 |     int x=sz(ss);
      |         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 60 queries.
2 Correct 3 ms 200 KB Guessed the password with 101 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 141 queries.
2 Correct 2 ms 200 KB Guessed the password with 136 queries.
3 Correct 8 ms 200 KB Guessed the password with 451 queries.
4 Correct 7 ms 200 KB Guessed the password with 523 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 468 KB Guessed the password with 8650 queries.
2 Correct 190 ms 416 KB Guessed the password with 11204 queries.
3 Correct 245 ms 404 KB Guessed the password with 14708 queries.
4 Correct 333 ms 428 KB Guessed the password with 18755 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 60 queries.
2 Correct 3 ms 200 KB Guessed the password with 101 queries.
3 Correct 3 ms 200 KB Guessed the password with 141 queries.
4 Correct 2 ms 200 KB Guessed the password with 136 queries.
5 Correct 8 ms 200 KB Guessed the password with 451 queries.
6 Correct 7 ms 200 KB Guessed the password with 523 queries.
7 Correct 89 ms 468 KB Guessed the password with 8650 queries.
8 Correct 190 ms 416 KB Guessed the password with 11204 queries.
9 Correct 245 ms 404 KB Guessed the password with 14708 queries.
10 Correct 333 ms 428 KB Guessed the password with 18755 queries.
11 Correct 413 ms 320 KB Guessed the password with 23251 queries.
12 Correct 518 ms 424 KB Guessed the password with 28238 queries.
13 Correct 553 ms 316 KB Guessed the password with 27968 queries.
14 Correct 589 ms 568 KB Guessed the password with 30064 queries.
15 Correct 587 ms 552 KB Guessed the password with 28951 queries.
16 Correct 579 ms 480 KB Guessed the password with 32882 queries.
17 Correct 634 ms 348 KB Guessed the password with 28829 queries.
18 Correct 705 ms 328 KB Guessed the password with 34117 queries.
19 Correct 587 ms 324 KB Guessed the password with 28346 queries.
20 Correct 816 ms 452 KB Guessed the password with 35268 queries.
21 Correct 714 ms 452 KB Guessed the password with 31875 queries.
22 Correct 690 ms 452 KB Guessed the password with 36377 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 60 queries.
2 Correct 3 ms 200 KB Guessed the password with 101 queries.
3 Correct 3 ms 200 KB Guessed the password with 141 queries.
4 Correct 2 ms 200 KB Guessed the password with 136 queries.
5 Correct 8 ms 200 KB Guessed the password with 451 queries.
6 Correct 7 ms 200 KB Guessed the password with 523 queries.
7 Correct 89 ms 468 KB Guessed the password with 8650 queries.
8 Correct 190 ms 416 KB Guessed the password with 11204 queries.
9 Correct 245 ms 404 KB Guessed the password with 14708 queries.
10 Correct 333 ms 428 KB Guessed the password with 18755 queries.
11 Correct 413 ms 320 KB Guessed the password with 23251 queries.
12 Correct 518 ms 424 KB Guessed the password with 28238 queries.
13 Correct 553 ms 316 KB Guessed the password with 27968 queries.
14 Correct 589 ms 568 KB Guessed the password with 30064 queries.
15 Correct 587 ms 552 KB Guessed the password with 28951 queries.
16 Correct 579 ms 480 KB Guessed the password with 32882 queries.
17 Correct 634 ms 348 KB Guessed the password with 28829 queries.
18 Correct 705 ms 328 KB Guessed the password with 34117 queries.
19 Correct 587 ms 324 KB Guessed the password with 28346 queries.
20 Correct 816 ms 452 KB Guessed the password with 35268 queries.
21 Correct 714 ms 452 KB Guessed the password with 31875 queries.
22 Correct 690 ms 452 KB Guessed the password with 36377 queries.
23 Incorrect 1162 ms 420 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -