oj.uz

Submission #529399

# Submission time Handle Problem Language Result Execution time Memory
529399 2022-02-23T01:35:50 Z i_am_noob Password (RMI18_password) C++17
80 / 100
 380 ms 804 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,n-cur-2);
                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,n-mid-1);
                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,n-l-1);
            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 200 KB Guessed the password with 31 queries.
3 Correct 1 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 23 ms 320 KB Guessed the password with 2143 queries.
2 Correct 54 ms 336 KB Guessed the password with 5940 queries.
3 Correct 36 ms 316 KB Guessed the password with 3598 queries.
4 Correct 110 ms 448 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 200 KB Guessed the password with 31 queries.
5 Correct 1 ms 200 KB Guessed the password with 6 queries.
6 Correct 1 ms 200 KB Guessed the password with 90 queries.
7 Correct 23 ms 320 KB Guessed the password with 2143 queries.
8 Correct 54 ms 336 KB Guessed the password with 5940 queries.
9 Correct 36 ms 316 KB Guessed the password with 3598 queries.
10 Correct 110 ms 448 KB Guessed the password with 10601 queries.
11 Correct 65 ms 396 KB Guessed the password with 6553 queries.
12 Correct 69 ms 464 KB Guessed the password with 6611 queries.
13 Correct 136 ms 392 KB Guessed the password with 14099 queries.
14 Correct 152 ms 504 KB Guessed the password with 14348 queries.
15 Correct 109 ms 508 KB Guessed the password with 11257 queries.
16 Correct 111 ms 540 KB Guessed the password with 11080 queries.
17 Correct 91 ms 472 KB Guessed the password with 8756 queries.
18 Correct 83 ms 416 KB Guessed the password with 8894 queries.
19 Correct 93 ms 560 KB Guessed the password with 7563 queries.
20 Correct 89 ms 356 KB Guessed the password with 7789 queries.
21 Correct 102 ms 420 KB Guessed the password with 9691 queries.
22 Correct 89 ms 396 KB Guessed the password with 8013 queries.

Subtask #5
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 200 KB Guessed the password with 31 queries.
5 Correct 1 ms 200 KB Guessed the password with 6 queries.
6 Correct 1 ms 200 KB Guessed the password with 90 queries.
7 Correct 23 ms 320 KB Guessed the password with 2143 queries.
8 Correct 54 ms 336 KB Guessed the password with 5940 queries.
9 Correct 36 ms 316 KB Guessed the password with 3598 queries.
10 Correct 110 ms 448 KB Guessed the password with 10601 queries.
11 Correct 65 ms 396 KB Guessed the password with 6553 queries.
12 Correct 69 ms 464 KB Guessed the password with 6611 queries.
13 Correct 136 ms 392 KB Guessed the password with 14099 queries.
14 Correct 152 ms 504 KB Guessed the password with 14348 queries.
15 Correct 109 ms 508 KB Guessed the password with 11257 queries.
16 Correct 111 ms 540 KB Guessed the password with 11080 queries.
17 Correct 91 ms 472 KB Guessed the password with 8756 queries.
18 Correct 83 ms 416 KB Guessed the password with 8894 queries.
19 Correct 93 ms 560 KB Guessed the password with 7563 queries.
20 Correct 89 ms 356 KB Guessed the password with 7789 queries.
21 Correct 102 ms 420 KB Guessed the password with 9691 queries.
22 Correct 89 ms 396 KB Guessed the password with 8013 queries.
23 Correct 327 ms 612 KB Guessed the password with 32357 queries.
24 Correct 263 ms 672 KB Guessed the password with 25356 queries.
25 Execution timed out 380 ms 804 KB Time limit exceeded (wall clock)
26 Halted 0 ms 0 KB -