oj.uz

답안 #854177

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854177 2023-09-26T09:55:00 Z TimDee Password (RMI18_password) C++17
100 / 100
 216 ms 1784 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;
      |                 ^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from password.cpp:12:
password.cpp: In function 'int ask(std::string)':
password.cpp:48:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     assert(s.size() <= n);
      |                     ^
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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Guessed the password with 81 queries.
2 Correct 1 ms 432 KB Guessed the password with 134 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 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 436 KB Guessed the password with 203 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 700 KB Guessed the password with 3237 queries.
2 Correct 31 ms 980 KB Guessed the password with 5109 queries.
3 Correct 33 ms 984 KB Guessed the password with 5851 queries.
4 Correct 48 ms 756 KB Guessed the password with 8522 queries.

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Guessed the password with 81 queries.
2 Correct 1 ms 432 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 436 KB Guessed the password with 203 queries.
7 Correct 17 ms 700 KB Guessed the password with 3237 queries.
8 Correct 31 ms 980 KB Guessed the password with 5109 queries.
9 Correct 33 ms 984 KB Guessed the password with 5851 queries.
10 Correct 48 ms 756 KB Guessed the password with 8522 queries.
11 Correct 86 ms 964 KB Guessed the password with 11552 queries.
12 Correct 85 ms 756 KB Guessed the password with 11532 queries.
13 Correct 99 ms 1012 KB Guessed the password with 13620 queries.
14 Correct 99 ms 1464 KB Guessed the password with 13625 queries.
15 Correct 109 ms 980 KB Guessed the password with 14061 queries.
16 Correct 107 ms 1028 KB Guessed the password with 14031 queries.
17 Correct 111 ms 960 KB Guessed the password with 13993 queries.
18 Correct 108 ms 972 KB Guessed the password with 14069 queries.
19 Correct 114 ms 760 KB Guessed the password with 13908 queries.
20 Correct 117 ms 1476 KB Guessed the password with 13956 queries.
21 Correct 121 ms 1224 KB Guessed the password with 15208 queries.
22 Correct 113 ms 1012 KB Guessed the password with 15204 queries.

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Guessed the password with 81 queries.
2 Correct 1 ms 432 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 436 KB Guessed the password with 203 queries.
7 Correct 17 ms 700 KB Guessed the password with 3237 queries.
8 Correct 31 ms 980 KB Guessed the password with 5109 queries.
9 Correct 33 ms 984 KB Guessed the password with 5851 queries.
10 Correct 48 ms 756 KB Guessed the password with 8522 queries.
11 Correct 86 ms 964 KB Guessed the password with 11552 queries.
12 Correct 85 ms 756 KB Guessed the password with 11532 queries.
13 Correct 99 ms 1012 KB Guessed the password with 13620 queries.
14 Correct 99 ms 1464 KB Guessed the password with 13625 queries.
15 Correct 109 ms 980 KB Guessed the password with 14061 queries.
16 Correct 107 ms 1028 KB Guessed the password with 14031 queries.
17 Correct 111 ms 960 KB Guessed the password with 13993 queries.
18 Correct 108 ms 972 KB Guessed the password with 14069 queries.
19 Correct 114 ms 760 KB Guessed the password with 13908 queries.
20 Correct 117 ms 1476 KB Guessed the password with 13956 queries.
21 Correct 121 ms 1224 KB Guessed the password with 15208 queries.
22 Correct 113 ms 1012 KB Guessed the password with 15204 queries.
23 Correct 214 ms 1688 KB Guessed the password with 24139 queries.
24 Correct 196 ms 1512 KB Guessed the password with 23288 queries.
25 Correct 207 ms 1760 KB Guessed the password with 24133 queries.
26 Correct 216 ms 1784 KB Guessed the password with 22699 queries.
27 Correct 210 ms 1248 KB Guessed the password with 24169 queries.
28 Correct 215 ms 1696 KB Guessed the password with 21811 queries.
29 Correct 210 ms 1516 KB Guessed the password with 24129 queries.
30 Correct 206 ms 1428 KB Guessed the password with 20531 queries.