oj.uz

Submission #433824

# Submission time Handle Problem Language Result Execution time Memory
433824 2021-06-20T11:06:49 Z AmineWeslati Password (RMI18_password) C++14
80 / 100
 1056 ms 564 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,0);
    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; 

    if(N<=3500) 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){
            	return ".";
            }

            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 2 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 141 queries.
2 Correct 3 ms 200 KB Guessed the password with 136 queries.
3 Correct 9 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 156 ms 288 KB Guessed the password with 8650 queries.
2 Correct 161 ms 300 KB Guessed the password with 11204 queries.
3 Correct 218 ms 320 KB Guessed the password with 14708 queries.
4 Correct 321 ms 320 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 2 ms 200 KB Guessed the password with 101 queries.
3 Correct 3 ms 200 KB Guessed the password with 141 queries.
4 Correct 3 ms 200 KB Guessed the password with 136 queries.
5 Correct 9 ms 200 KB Guessed the password with 451 queries.
6 Correct 7 ms 200 KB Guessed the password with 523 queries.
7 Correct 156 ms 288 KB Guessed the password with 8650 queries.
8 Correct 161 ms 300 KB Guessed the password with 11204 queries.
9 Correct 218 ms 320 KB Guessed the password with 14708 queries.
10 Correct 321 ms 320 KB Guessed the password with 18755 queries.
11 Correct 492 ms 324 KB Guessed the password with 23251 queries.
12 Correct 549 ms 428 KB Guessed the password with 28238 queries.
13 Correct 610 ms 312 KB Guessed the password with 27968 queries.
14 Correct 608 ms 432 KB Guessed the password with 30064 queries.
15 Correct 602 ms 320 KB Guessed the password with 28951 queries.
16 Correct 570 ms 328 KB Guessed the password with 32882 queries.
17 Correct 610 ms 336 KB Guessed the password with 28829 queries.
18 Correct 723 ms 564 KB Guessed the password with 34117 queries.
19 Correct 640 ms 444 KB Guessed the password with 28346 queries.
20 Correct 653 ms 416 KB Guessed the password with 35268 queries.
21 Correct 681 ms 452 KB Guessed the password with 31875 queries.
22 Correct 696 ms 332 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 2 ms 200 KB Guessed the password with 101 queries.
3 Correct 3 ms 200 KB Guessed the password with 141 queries.
4 Correct 3 ms 200 KB Guessed the password with 136 queries.
5 Correct 9 ms 200 KB Guessed the password with 451 queries.
6 Correct 7 ms 200 KB Guessed the password with 523 queries.
7 Correct 156 ms 288 KB Guessed the password with 8650 queries.
8 Correct 161 ms 300 KB Guessed the password with 11204 queries.
9 Correct 218 ms 320 KB Guessed the password with 14708 queries.
10 Correct 321 ms 320 KB Guessed the password with 18755 queries.
11 Correct 492 ms 324 KB Guessed the password with 23251 queries.
12 Correct 549 ms 428 KB Guessed the password with 28238 queries.
13 Correct 610 ms 312 KB Guessed the password with 27968 queries.
14 Correct 608 ms 432 KB Guessed the password with 30064 queries.
15 Correct 602 ms 320 KB Guessed the password with 28951 queries.
16 Correct 570 ms 328 KB Guessed the password with 32882 queries.
17 Correct 610 ms 336 KB Guessed the password with 28829 queries.
18 Correct 723 ms 564 KB Guessed the password with 34117 queries.
19 Correct 640 ms 444 KB Guessed the password with 28346 queries.
20 Correct 653 ms 416 KB Guessed the password with 35268 queries.
21 Correct 681 ms 452 KB Guessed the password with 31875 queries.
22 Correct 696 ms 332 KB Guessed the password with 36377 queries.
23 Incorrect 1056 ms 348 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -