oj.uz

Submission #529404

# Submission time Handle Problem Language Result Execution time Memory
529404 2022-02-23T01:43:26 Z i_am_noob Password (RMI18_password) C++17
100 / 100
 445 ms 816 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*david){
                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 67 queries.
2 Correct 2 ms 200 KB Guessed the password with 133 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 212 KB Guessed the password with 31 queries.
3 Correct 1 ms 328 KB Guessed the password with 6 queries.
4 Correct 1 ms 292 KB Guessed the password with 90 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 296 KB Guessed the password with 2143 queries.
2 Correct 58 ms 364 KB Guessed the password with 5940 queries.
3 Correct 37 ms 308 KB Guessed the password with 3598 queries.
4 Correct 109 ms 400 KB Guessed the password with 10601 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 67 queries.
2 Correct 2 ms 200 KB Guessed the password with 133 queries.
3 Correct 1 ms 200 KB Guessed the password with 24 queries.
4 Correct 1 ms 212 KB Guessed the password with 31 queries.
5 Correct 1 ms 328 KB Guessed the password with 6 queries.
6 Correct 1 ms 292 KB Guessed the password with 90 queries.
7 Correct 11 ms 296 KB Guessed the password with 2143 queries.
8 Correct 58 ms 364 KB Guessed the password with 5940 queries.
9 Correct 37 ms 308 KB Guessed the password with 3598 queries.
10 Correct 109 ms 400 KB Guessed the password with 10601 queries.
11 Correct 64 ms 424 KB Guessed the password with 6553 queries.
12 Correct 72 ms 380 KB Guessed the password with 6611 queries.
13 Correct 145 ms 432 KB Guessed the password with 14099 queries.
14 Correct 148 ms 512 KB Guessed the password with 14348 queries.
15 Correct 96 ms 448 KB Guessed the password with 11257 queries.
16 Correct 107 ms 444 KB Guessed the password with 11080 queries.
17 Correct 93 ms 452 KB Guessed the password with 8756 queries.
18 Correct 101 ms 576 KB Guessed the password with 8894 queries.
19 Correct 77 ms 448 KB Guessed the password with 7563 queries.
20 Correct 46 ms 460 KB Guessed the password with 7789 queries.
21 Correct 134 ms 448 KB Guessed the password with 9691 queries.
22 Correct 85 ms 460 KB Guessed the password with 8013 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 67 queries.
2 Correct 2 ms 200 KB Guessed the password with 133 queries.
3 Correct 1 ms 200 KB Guessed the password with 24 queries.
4 Correct 1 ms 212 KB Guessed the password with 31 queries.
5 Correct 1 ms 328 KB Guessed the password with 6 queries.
6 Correct 1 ms 292 KB Guessed the password with 90 queries.
7 Correct 11 ms 296 KB Guessed the password with 2143 queries.
8 Correct 58 ms 364 KB Guessed the password with 5940 queries.
9 Correct 37 ms 308 KB Guessed the password with 3598 queries.
10 Correct 109 ms 400 KB Guessed the password with 10601 queries.
11 Correct 64 ms 424 KB Guessed the password with 6553 queries.
12 Correct 72 ms 380 KB Guessed the password with 6611 queries.
13 Correct 145 ms 432 KB Guessed the password with 14099 queries.
14 Correct 148 ms 512 KB Guessed the password with 14348 queries.
15 Correct 96 ms 448 KB Guessed the password with 11257 queries.
16 Correct 107 ms 444 KB Guessed the password with 11080 queries.
17 Correct 93 ms 452 KB Guessed the password with 8756 queries.
18 Correct 101 ms 576 KB Guessed the password with 8894 queries.
19 Correct 77 ms 448 KB Guessed the password with 7563 queries.
20 Correct 46 ms 460 KB Guessed the password with 7789 queries.
21 Correct 134 ms 448 KB Guessed the password with 9691 queries.
22 Correct 85 ms 460 KB Guessed the password with 8013 queries.
23 Correct 345 ms 628 KB Guessed the password with 32357 queries.
24 Correct 230 ms 616 KB Guessed the password with 25356 queries.
25 Correct 382 ms 816 KB Guessed the password with 39642 queries.
26 Correct 205 ms 628 KB Guessed the password with 22840 queries.
27 Correct 445 ms 636 KB Guessed the password with 42655 queries.
28 Correct 181 ms 632 KB Guessed the password with 16990 queries.
29 Correct 294 ms 752 KB Guessed the password with 42796 queries.
30 Correct 105 ms 516 KB Guessed the password with 11402 queries.