oj.uz

Submission #433759

# Submission time Handle Problem Language Result Execution time Memory
433759 2021-06-20T10:29:55 Z AmineWeslati Password (RMI18_password) C++14
80 / 100
 1214 ms 560 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,min(idx,sz(s))) ss+=s[i];
    ss+=c; 

    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=1;

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 60 queries.
2 Correct 2 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 130 queries.
2 Correct 6 ms 200 KB Guessed the password with 335 queries.
3 Correct 7 ms 200 KB Guessed the password with 471 queries.
4 Correct 5 ms 200 KB Guessed the password with 345 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 280 KB Guessed the password with 8650 queries.
2 Correct 159 ms 296 KB Guessed the password with 11146 queries.
3 Correct 192 ms 316 KB Guessed the password with 12326 queries.
4 Correct 293 ms 316 KB Guessed the password with 18536 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 60 queries.
2 Correct 2 ms 200 KB Guessed the password with 101 queries.
3 Correct 3 ms 200 KB Guessed the password with 130 queries.
4 Correct 6 ms 200 KB Guessed the password with 335 queries.
5 Correct 7 ms 200 KB Guessed the password with 471 queries.
6 Correct 5 ms 200 KB Guessed the password with 345 queries.
7 Correct 111 ms 280 KB Guessed the password with 8650 queries.
8 Correct 159 ms 296 KB Guessed the password with 11146 queries.
9 Correct 192 ms 316 KB Guessed the password with 12326 queries.
10 Correct 293 ms 316 KB Guessed the password with 18536 queries.
11 Correct 478 ms 424 KB Guessed the password with 23368 queries.
12 Correct 501 ms 472 KB Guessed the password with 28238 queries.
13 Correct 527 ms 324 KB Guessed the password with 28149 queries.
14 Correct 593 ms 340 KB Guessed the password with 30400 queries.
15 Correct 616 ms 332 KB Guessed the password with 29255 queries.
16 Correct 605 ms 412 KB Guessed the password with 32281 queries.
17 Correct 479 ms 348 KB Guessed the password with 29096 queries.
18 Correct 709 ms 408 KB Guessed the password with 34117 queries.
19 Correct 603 ms 328 KB Guessed the password with 29177 queries.
20 Correct 734 ms 452 KB Guessed the password with 34727 queries.
21 Correct 665 ms 456 KB Guessed the password with 31976 queries.
22 Correct 599 ms 560 KB Guessed the password with 36370 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 60 queries.
2 Correct 2 ms 200 KB Guessed the password with 101 queries.
3 Correct 3 ms 200 KB Guessed the password with 130 queries.
4 Correct 6 ms 200 KB Guessed the password with 335 queries.
5 Correct 7 ms 200 KB Guessed the password with 471 queries.
6 Correct 5 ms 200 KB Guessed the password with 345 queries.
7 Correct 111 ms 280 KB Guessed the password with 8650 queries.
8 Correct 159 ms 296 KB Guessed the password with 11146 queries.
9 Correct 192 ms 316 KB Guessed the password with 12326 queries.
10 Correct 293 ms 316 KB Guessed the password with 18536 queries.
11 Correct 478 ms 424 KB Guessed the password with 23368 queries.
12 Correct 501 ms 472 KB Guessed the password with 28238 queries.
13 Correct 527 ms 324 KB Guessed the password with 28149 queries.
14 Correct 593 ms 340 KB Guessed the password with 30400 queries.
15 Correct 616 ms 332 KB Guessed the password with 29255 queries.
16 Correct 605 ms 412 KB Guessed the password with 32281 queries.
17 Correct 479 ms 348 KB Guessed the password with 29096 queries.
18 Correct 709 ms 408 KB Guessed the password with 34117 queries.
19 Correct 603 ms 328 KB Guessed the password with 29177 queries.
20 Correct 734 ms 452 KB Guessed the password with 34727 queries.
21 Correct 665 ms 456 KB Guessed the password with 31976 queries.
22 Correct 599 ms 560 KB Guessed the password with 36370 queries.
23 Incorrect 1214 ms 428 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -