oj.uz

Submission #529396

# Submission time Handle Problem Language Result Execution time Memory
529396 2022-02-23T01:31:57 Z i_am_noob Password (RMI18_password) C++17
80 / 100
 1070 ms 712 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];

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);
    }
    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);
                while(sz(str)<n) str+='a'+t;
                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.clear();
                str=res.substr(0,mid+1);
                while(sz(str)<n) str+='a'+t;
                int y=query(str)-mid-1;
                if(y<x) r=mid;
                else l=mid+1;
            }
            str.clear();
            str=res.substr(0,l+1);
            while(sz(str)<n) str+='a'+t;
            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:99:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |                 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 0 ms 280 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 31 ms 296 KB Guessed the password with 2143 queries.
2 Correct 83 ms 320 KB Guessed the password with 5940 queries.
3 Correct 62 ms 308 KB Guessed the password with 3598 queries.
4 Correct 185 ms 328 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 0 ms 280 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 31 ms 296 KB Guessed the password with 2143 queries.
8 Correct 83 ms 320 KB Guessed the password with 5940 queries.
9 Correct 62 ms 308 KB Guessed the password with 3598 queries.
10 Correct 185 ms 328 KB Guessed the password with 10601 queries.
11 Correct 106 ms 324 KB Guessed the password with 6553 queries.
12 Correct 140 ms 320 KB Guessed the password with 6611 queries.
13 Correct 291 ms 320 KB Guessed the password with 14099 queries.
14 Correct 276 ms 568 KB Guessed the password with 14348 queries.
15 Correct 201 ms 572 KB Guessed the password with 11257 queries.
16 Correct 231 ms 436 KB Guessed the password with 11080 queries.
17 Correct 202 ms 436 KB Guessed the password with 8756 queries.
18 Correct 187 ms 456 KB Guessed the password with 8894 queries.
19 Correct 175 ms 452 KB Guessed the password with 7563 queries.
20 Correct 155 ms 436 KB Guessed the password with 7789 queries.
21 Correct 222 ms 456 KB Guessed the password with 9691 queries.
22 Correct 197 ms 324 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 0 ms 280 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 31 ms 296 KB Guessed the password with 2143 queries.
8 Correct 83 ms 320 KB Guessed the password with 5940 queries.
9 Correct 62 ms 308 KB Guessed the password with 3598 queries.
10 Correct 185 ms 328 KB Guessed the password with 10601 queries.
11 Correct 106 ms 324 KB Guessed the password with 6553 queries.
12 Correct 140 ms 320 KB Guessed the password with 6611 queries.
13 Correct 291 ms 320 KB Guessed the password with 14099 queries.
14 Correct 276 ms 568 KB Guessed the password with 14348 queries.
15 Correct 201 ms 572 KB Guessed the password with 11257 queries.
16 Correct 231 ms 436 KB Guessed the password with 11080 queries.
17 Correct 202 ms 436 KB Guessed the password with 8756 queries.
18 Correct 187 ms 456 KB Guessed the password with 8894 queries.
19 Correct 175 ms 452 KB Guessed the password with 7563 queries.
20 Correct 155 ms 436 KB Guessed the password with 7789 queries.
21 Correct 222 ms 456 KB Guessed the password with 9691 queries.
22 Correct 197 ms 324 KB Guessed the password with 8013 queries.
23 Correct 941 ms 476 KB Guessed the password with 32357 queries.
24 Correct 748 ms 604 KB Guessed the password with 25356 queries.
25 Execution timed out 1070 ms 712 KB Time limit exceeded (wall clock)
26 Halted 0 ms 0 KB -