oj.uz

Submission #529406

# Submission time Handle Problem Language Result Execution time Memory
529406 2022-02-23T01:46:05 Z i_am_noob Password (RMI18_password) C++17
100 / 100
 409 ms 744 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
//#define int ll
#define ull unsigned ll
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define chkmin(a,b) (a=min(a,b))
#define chkmax(a,b) (a=max(a,b))
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif
template<typename T> void print(T && x) {cout << x << "\n";}
template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;

const int maxn=5005,maxm=32,maxk=7777714;

//i_am_noob
//#define wiwihorz  
int query(string str);

int cnt[26];
string letters[26];

const int david=13;

string guess(int n, int s){
    string res;
    memset(cnt,0,sizeof cnt);
    rep(s){
        string str;
        rep1(j,n) str+='a'+i;
        cnt[i]=query(str);
        letters[i]=str;
    }
    vector<int> id;
    rep(s) id.pb(i);
    sort(all(id),[](int i, int j){return cnt[i]<cnt[j];});
    for(auto t: id){
        if(res.empty()){
            rep(cnt[t]) res+='a'+t;
            continue;
        }
        string str;
        str+=res[0];
        while(sz(str)<n) str+='a'+t;
        int x=query(str)-1;
        string nres;
        rep(cnt[t]-x) nres+='a'+t;
        int cur=0;
        while(cur<sz(res)){
            if(x==0){
                nres+=res[cur];
                cur++;
                continue;
            }
            if(cur==sz(res)-1){
                nres+=res[cur];
                rep(x) nres+='a'+t;
                cur++;
                break;
            }
            if(sz(res)-cur<x*(__lg(sz(res)-cur+1)+1)){
                str=res.substr(0,cur+2)+letters[t].substr(0,x);
                int y=query(str)-cur-2;
                nres+=res[cur];
                rep(x-y) nres+='a'+t;
                cur++;
                x=y;
                continue;
            }
            int l=cur+1,r=sz(res)-1;
            while(l<r){
                int mid=l+r>>1;
                str=res.substr(0,mid+1)+letters[t].substr(0,x);
                int y=query(str)-mid-1;
                if(y<x) r=mid;
                else l=mid+1;
            }
            str=res.substr(0,l+1)+letters[t].substr(0,x);
            int y=query(str)-l-1;
            while(cur<l) nres+=res[cur],cur++;
            rep(x-y) nres+='a'+t;
            x=y;
        }
        res=nres;
        //cout << res << "\n";
    }
    return res;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:100:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |                 int mid=l+r>>1;
      |                         ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 69 queries.
2 Correct 2 ms 200 KB Guessed the password with 132 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 24 queries.
2 Correct 1 ms 200 KB Guessed the password with 31 queries.
3 Correct 0 ms 200 KB Guessed the password with 6 queries.
4 Correct 1 ms 200 KB Guessed the password with 90 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 316 KB Guessed the password with 2140 queries.
2 Correct 58 ms 328 KB Guessed the password with 6034 queries.
3 Correct 39 ms 324 KB Guessed the password with 3599 queries.
4 Correct 78 ms 472 KB Guessed the password with 11059 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 69 queries.
2 Correct 2 ms 200 KB Guessed the password with 132 queries.
3 Correct 1 ms 200 KB Guessed the password with 24 queries.
4 Correct 1 ms 200 KB Guessed the password with 31 queries.
5 Correct 0 ms 200 KB Guessed the password with 6 queries.
6 Correct 1 ms 200 KB Guessed the password with 90 queries.
7 Correct 21 ms 316 KB Guessed the password with 2140 queries.
8 Correct 58 ms 328 KB Guessed the password with 6034 queries.
9 Correct 39 ms 324 KB Guessed the password with 3599 queries.
10 Correct 78 ms 472 KB Guessed the password with 11059 queries.
11 Correct 70 ms 420 KB Guessed the password with 6568 queries.
12 Correct 96 ms 536 KB Guessed the password with 6595 queries.
13 Correct 113 ms 556 KB Guessed the password with 14177 queries.
14 Correct 151 ms 448 KB Guessed the password with 14611 queries.
15 Correct 98 ms 448 KB Guessed the password with 11230 queries.
16 Correct 125 ms 444 KB Guessed the password with 11138 queries.
17 Correct 119 ms 456 KB Guessed the password with 8795 queries.
18 Correct 77 ms 444 KB Guessed the password with 8875 queries.
19 Correct 85 ms 528 KB Guessed the password with 7551 queries.
20 Correct 70 ms 580 KB Guessed the password with 7776 queries.
21 Correct 100 ms 452 KB Guessed the password with 9929 queries.
22 Correct 84 ms 456 KB Guessed the password with 8157 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 69 queries.
2 Correct 2 ms 200 KB Guessed the password with 132 queries.
3 Correct 1 ms 200 KB Guessed the password with 24 queries.
4 Correct 1 ms 200 KB Guessed the password with 31 queries.
5 Correct 0 ms 200 KB Guessed the password with 6 queries.
6 Correct 1 ms 200 KB Guessed the password with 90 queries.
7 Correct 21 ms 316 KB Guessed the password with 2140 queries.
8 Correct 58 ms 328 KB Guessed the password with 6034 queries.
9 Correct 39 ms 324 KB Guessed the password with 3599 queries.
10 Correct 78 ms 472 KB Guessed the password with 11059 queries.
11 Correct 70 ms 420 KB Guessed the password with 6568 queries.
12 Correct 96 ms 536 KB Guessed the password with 6595 queries.
13 Correct 113 ms 556 KB Guessed the password with 14177 queries.
14 Correct 151 ms 448 KB Guessed the password with 14611 queries.
15 Correct 98 ms 448 KB Guessed the password with 11230 queries.
16 Correct 125 ms 444 KB Guessed the password with 11138 queries.
17 Correct 119 ms 456 KB Guessed the password with 8795 queries.
18 Correct 77 ms 444 KB Guessed the password with 8875 queries.
19 Correct 85 ms 528 KB Guessed the password with 7551 queries.
20 Correct 70 ms 580 KB Guessed the password with 7776 queries.
21 Correct 100 ms 452 KB Guessed the password with 9929 queries.
22 Correct 84 ms 456 KB Guessed the password with 8157 queries.
23 Correct 370 ms 712 KB Guessed the password with 30888 queries.
24 Correct 228 ms 628 KB Guessed the password with 25747 queries.
25 Correct 409 ms 540 KB Guessed the password with 38946 queries.
26 Correct 252 ms 672 KB Guessed the password with 23299 queries.
27 Correct 285 ms 744 KB Guessed the password with 41402 queries.
28 Correct 151 ms 564 KB Guessed the password with 16979 queries.
29 Correct 296 ms 600 KB Guessed the password with 42405 queries.
30 Correct 115 ms 496 KB Guessed the password with 11388 queries.