oj.uz

Submission #854179

# Submission time Handle Problem Language Result Execution time Memory
854179 2023-09-26T09:56:58 Z TimDee Password (RMI18_password) C++17
100 / 100
 214 ms 1760 KB 
//  Esti <3

//\
     šťastia pre nás :)
//   you're already the best
//             _
//   ^ ^      //
// >(O_O)<___//
//   \ __ __  \
//    \\ \\ \\\\
 
#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3","unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")

using ll = long long;
//#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = 1e18;
const int mod = 998244353;
 
// \
\
:smiling_face_with_3_hearts: :smiling_face_with_3_hearts:  :smiling_face_with_3_hearts:  
 
//vidime sa veľmi skoro, moje slnko

string pass;

int query(string s);

int n;
int ask(string s) {
    //assert(s.size() <= n);
    return query(s);
}

int Q=0;
void insert(string&s, int i, char c) {
    s+=c;
    for (int j=s.size()-1; j>i; --j) {
        swap(s[j],s[j-1]);
    }
}
void erase(string&s, int i) {
    for (int j=i; j+1 < s.size(); ++j) swap(s[j], s[j+1]);
    s.pop_back();
}

string merge(string f, string s) {
    int p=f.size();
    int n=s.size()-1;
    int old = ask(f);
    while (n>=0 && p>=0) {
        insert(f,p,s[n]);
        int x = ask(f);
        if (x > old) {
            old = x;
            --n;
        } else {
            erase(f,p);
            --p;
        }
    }
    while (n>=0) insert(f,0,s[n--]);
    return f;
}

string guess(int n, int s) {

    ::n=n;
    vector<int> cnt(s,0);
    for(char c='a'; c<(char)('a'+s); ++c) {
        string str;
        forn(i,n) str+=c;
        int x = ask(str);
        cnt[c-'a']=x;
    }
    vector<pi> v;
    forn(i,s) if (cnt[i]) v.pb({cnt[i],i});
    sort(all(v));
    
    vector<string> a;
    for(auto&x:v) a.pb(string(x.f,(char)('a'+x.s)));

    while (a.size()>1) {
        vector<string> b;
        int n=a.size();
        for(int i=0; i+1<n; i+=2) {
            //cout<<a[i]<<" & "<<a[i+1]<<": ";
            string z = merge(a[i],a[i+1]);
            //cout<<z<<'\n';
            b.pb(z);
        }
        if (n&1) b.pb(a[n-1]);
        a=b;
    }
    return a[0];

}

Compilation message

password.cpp:3:1: warning: multi-line comment [-Wcomment]
    3 | //\
      | ^
password.cpp:9:1: warning: multi-line comment [-Wcomment]
    9 | //   \ __ __  \
      | ^
password.cpp:36:1: warning: multi-line comment [-Wcomment]
   36 | // \
      | ^
password.cpp:33:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   33 | const int inf = 1e18;
      |                 ^~~~
password.cpp: In function 'void erase(std::string&, int)':
password.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int j=i; j+1 < s.size(); ++j) swap(s[j], s[j+1]);
      |                   ~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 81 queries.
2 Correct 1 ms 440 KB Guessed the password with 134 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 53 queries.
2 Correct 1 ms 344 KB Guessed the password with 97 queries.
3 Correct 1 ms 344 KB Guessed the password with 107 queries.
4 Correct 1 ms 440 KB Guessed the password with 203 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 956 KB Guessed the password with 3237 queries.
2 Correct 30 ms 944 KB Guessed the password with 5109 queries.
3 Correct 34 ms 980 KB Guessed the password with 5851 queries.
4 Correct 52 ms 1020 KB Guessed the password with 8522 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 81 queries.
2 Correct 1 ms 440 KB Guessed the password with 134 queries.
3 Correct 1 ms 344 KB Guessed the password with 53 queries.
4 Correct 1 ms 344 KB Guessed the password with 97 queries.
5 Correct 1 ms 344 KB Guessed the password with 107 queries.
6 Correct 1 ms 440 KB Guessed the password with 203 queries.
7 Correct 23 ms 956 KB Guessed the password with 3237 queries.
8 Correct 30 ms 944 KB Guessed the password with 5109 queries.
9 Correct 34 ms 980 KB Guessed the password with 5851 queries.
10 Correct 52 ms 1020 KB Guessed the password with 8522 queries.
11 Correct 86 ms 964 KB Guessed the password with 11552 queries.
12 Correct 81 ms 728 KB Guessed the password with 11532 queries.
13 Correct 105 ms 1524 KB Guessed the password with 13620 queries.
14 Correct 101 ms 716 KB Guessed the password with 13625 queries.
15 Correct 111 ms 704 KB Guessed the password with 14061 queries.
16 Correct 102 ms 1476 KB Guessed the password with 14031 queries.
17 Correct 108 ms 1012 KB Guessed the password with 13993 queries.
18 Correct 109 ms 1236 KB Guessed the password with 14069 queries.
19 Correct 110 ms 772 KB Guessed the password with 13908 queries.
20 Correct 107 ms 1484 KB Guessed the password with 13956 queries.
21 Correct 128 ms 772 KB Guessed the password with 15208 queries.
22 Correct 122 ms 980 KB Guessed the password with 15204 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 81 queries.
2 Correct 1 ms 440 KB Guessed the password with 134 queries.
3 Correct 1 ms 344 KB Guessed the password with 53 queries.
4 Correct 1 ms 344 KB Guessed the password with 97 queries.
5 Correct 1 ms 344 KB Guessed the password with 107 queries.
6 Correct 1 ms 440 KB Guessed the password with 203 queries.
7 Correct 23 ms 956 KB Guessed the password with 3237 queries.
8 Correct 30 ms 944 KB Guessed the password with 5109 queries.
9 Correct 34 ms 980 KB Guessed the password with 5851 queries.
10 Correct 52 ms 1020 KB Guessed the password with 8522 queries.
11 Correct 86 ms 964 KB Guessed the password with 11552 queries.
12 Correct 81 ms 728 KB Guessed the password with 11532 queries.
13 Correct 105 ms 1524 KB Guessed the password with 13620 queries.
14 Correct 101 ms 716 KB Guessed the password with 13625 queries.
15 Correct 111 ms 704 KB Guessed the password with 14061 queries.
16 Correct 102 ms 1476 KB Guessed the password with 14031 queries.
17 Correct 108 ms 1012 KB Guessed the password with 13993 queries.
18 Correct 109 ms 1236 KB Guessed the password with 14069 queries.
19 Correct 110 ms 772 KB Guessed the password with 13908 queries.
20 Correct 107 ms 1484 KB Guessed the password with 13956 queries.
21 Correct 128 ms 772 KB Guessed the password with 15208 queries.
22 Correct 122 ms 980 KB Guessed the password with 15204 queries.
23 Correct 202 ms 1688 KB Guessed the password with 24139 queries.
24 Correct 199 ms 1384 KB Guessed the password with 23288 queries.
25 Correct 214 ms 1524 KB Guessed the password with 24133 queries.
26 Correct 211 ms 1760 KB Guessed the password with 22699 queries.
27 Correct 206 ms 1332 KB Guessed the password with 24169 queries.
28 Correct 212 ms 1608 KB Guessed the password with 21811 queries.
29 Correct 197 ms 1520 KB Guessed the password with 24129 queries.
30 Correct 190 ms 1436 KB Guessed the password with 20531 queries.