oj.uz

Submission #854130

# Submission time Handle Problem Language Result Execution time Memory
854130 2023-09-26T07:57:26 Z TimDee Password (RMI18_password) C++17
80 / 100
 544 ms 1728 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 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 guess(int n, int s) {

    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));
    int k=v.size();

    string ans(v[0].f,(char)('a'+v[0].s));

    for (int i=1; i<k; ++i) {
        char c = 'a'+v[i].s;
        int p=ans.size();
        int last = query(ans);
        while (p>=0 && v[i].f) {
            insert(ans,p,c);
            int x = query(ans);
            if (x > last) {
                last = x; 
                --v[i].f;
            } else {
                erase(ans,p);
                --p;
            }
        }
        forn(j,v[i].f) insert(ans,0,c);
    }
    return ans;

}

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:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     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 101 queries.
2 Correct 1 ms 344 KB Guessed the password with 178 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 344 KB Guessed the password with 178 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1208 KB Guessed the password with 3146 queries.
2 Correct 60 ms 952 KB Guessed the password with 9576 queries.
3 Correct 32 ms 940 KB Guessed the password with 5211 queries.
4 Correct 104 ms 704 KB Guessed the password with 13940 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 101 queries.
2 Correct 1 ms 344 KB Guessed the password with 178 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 344 KB Guessed the password with 178 queries.
7 Correct 22 ms 1208 KB Guessed the password with 3146 queries.
8 Correct 60 ms 952 KB Guessed the password with 9576 queries.
9 Correct 32 ms 940 KB Guessed the password with 5211 queries.
10 Correct 104 ms 704 KB Guessed the password with 13940 queries.
11 Correct 74 ms 696 KB Guessed the password with 9375 queries.
12 Correct 88 ms 1192 KB Guessed the password with 9399 queries.
13 Correct 155 ms 952 KB Guessed the password with 17898 queries.
14 Correct 152 ms 696 KB Guessed the password with 18292 queries.
15 Correct 123 ms 1204 KB Guessed the password with 14439 queries.
16 Correct 117 ms 704 KB Guessed the password with 14351 queries.
17 Correct 107 ms 708 KB Guessed the password with 12186 queries.
18 Correct 107 ms 688 KB Guessed the password with 12245 queries.
19 Correct 91 ms 952 KB Guessed the password with 10971 queries.
20 Correct 104 ms 700 KB Guessed the password with 11188 queries.
21 Correct 131 ms 700 KB Guessed the password with 15181 queries.
22 Correct 127 ms 708 KB Guessed the password with 15270 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 101 queries.
2 Correct 1 ms 344 KB Guessed the password with 178 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 344 KB Guessed the password with 178 queries.
7 Correct 22 ms 1208 KB Guessed the password with 3146 queries.
8 Correct 60 ms 952 KB Guessed the password with 9576 queries.
9 Correct 32 ms 940 KB Guessed the password with 5211 queries.
10 Correct 104 ms 704 KB Guessed the password with 13940 queries.
11 Correct 74 ms 696 KB Guessed the password with 9375 queries.
12 Correct 88 ms 1192 KB Guessed the password with 9399 queries.
13 Correct 155 ms 952 KB Guessed the password with 17898 queries.
14 Correct 152 ms 696 KB Guessed the password with 18292 queries.
15 Correct 123 ms 1204 KB Guessed the password with 14439 queries.
16 Correct 117 ms 704 KB Guessed the password with 14351 queries.
17 Correct 107 ms 708 KB Guessed the password with 12186 queries.
18 Correct 107 ms 688 KB Guessed the password with 12245 queries.
19 Correct 91 ms 952 KB Guessed the password with 10971 queries.
20 Correct 104 ms 700 KB Guessed the password with 11188 queries.
21 Correct 131 ms 700 KB Guessed the password with 15181 queries.
22 Correct 127 ms 708 KB Guessed the password with 15270 queries.
23 Incorrect 544 ms 1728 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -