oj.uz

Submission #854180

# Submission time Handle Problem Language Result Execution time Memory
854180 2023-09-26T09:58:27 Z TimDee Password (RMI18_password) C++17
100 / 100
 217 ms 1764 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 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 = query(f);
    while (n>=0 && p>=0) {
        insert(f,p,s[n]);
        int x = query(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 = query(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:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     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 444 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 2 ms 344 KB Guessed the password with 203 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 960 KB Guessed the password with 3237 queries.
2 Correct 28 ms 1208 KB Guessed the password with 5109 queries.
3 Correct 34 ms 1224 KB Guessed the password with 5851 queries.
4 Correct 54 ms 1460 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 444 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 2 ms 344 KB Guessed the password with 203 queries.
7 Correct 16 ms 960 KB Guessed the password with 3237 queries.
8 Correct 28 ms 1208 KB Guessed the password with 5109 queries.
9 Correct 34 ms 1224 KB Guessed the password with 5851 queries.
10 Correct 54 ms 1460 KB Guessed the password with 8522 queries.
11 Correct 96 ms 732 KB Guessed the password with 11552 queries.
12 Correct 80 ms 956 KB Guessed the password with 11532 queries.
13 Correct 99 ms 1212 KB Guessed the password with 13620 queries.
14 Correct 97 ms 996 KB Guessed the password with 13625 queries.
15 Correct 115 ms 960 KB Guessed the password with 14061 queries.
16 Correct 106 ms 728 KB Guessed the password with 14031 queries.
17 Correct 110 ms 976 KB Guessed the password with 13993 queries.
18 Correct 123 ms 952 KB Guessed the password with 14069 queries.
19 Correct 107 ms 728 KB Guessed the password with 13908 queries.
20 Correct 116 ms 720 KB Guessed the password with 13956 queries.
21 Correct 121 ms 952 KB Guessed the password with 15208 queries.
22 Correct 110 ms 716 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 444 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 2 ms 344 KB Guessed the password with 203 queries.
7 Correct 16 ms 960 KB Guessed the password with 3237 queries.
8 Correct 28 ms 1208 KB Guessed the password with 5109 queries.
9 Correct 34 ms 1224 KB Guessed the password with 5851 queries.
10 Correct 54 ms 1460 KB Guessed the password with 8522 queries.
11 Correct 96 ms 732 KB Guessed the password with 11552 queries.
12 Correct 80 ms 956 KB Guessed the password with 11532 queries.
13 Correct 99 ms 1212 KB Guessed the password with 13620 queries.
14 Correct 97 ms 996 KB Guessed the password with 13625 queries.
15 Correct 115 ms 960 KB Guessed the password with 14061 queries.
16 Correct 106 ms 728 KB Guessed the password with 14031 queries.
17 Correct 110 ms 976 KB Guessed the password with 13993 queries.
18 Correct 123 ms 952 KB Guessed the password with 14069 queries.
19 Correct 107 ms 728 KB Guessed the password with 13908 queries.
20 Correct 116 ms 720 KB Guessed the password with 13956 queries.
21 Correct 121 ms 952 KB Guessed the password with 15208 queries.
22 Correct 110 ms 716 KB Guessed the password with 15204 queries.
23 Correct 208 ms 1436 KB Guessed the password with 24139 queries.
24 Correct 190 ms 1468 KB Guessed the password with 23288 queries.
25 Correct 195 ms 1496 KB Guessed the password with 24133 queries.
26 Correct 200 ms 968 KB Guessed the password with 22699 queries.
27 Correct 195 ms 1512 KB Guessed the password with 24169 queries.
28 Correct 217 ms 1508 KB Guessed the password with 21811 queries.
29 Correct 215 ms 1764 KB Guessed the password with 24129 queries.
30 Correct 204 ms 1304 KB Guessed the password with 20531 queries.