oj.uz

Submission #519406

# Submission time Handle Problem Language Result Execution time Memory
519406 2022-01-26T10:20:29 Z hohohaha Password (RMI18_password) C++14
100 / 100
 300 ms 660 KB 
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld, ld> pld;
typedef vector<pi> vpi;
 
//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
    os << "[";
    for (int i = 0; i < ll(a.size()); i++) { os << a[i] << ((i != ll(a.size() - 1) ? " " : "")); }
    os << "]\n";
    return os;
}
 
#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map
 
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}
 
template<typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> &p) {
    os << "" << p.first << " " << p.second << "";
    return os;
}
 
void usaco(string taskname) {
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char *FIN = fin.c_str();
    const char *FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}
 
template<typename T>
void read(vector<T> &v) {
    int n = v.size();
    for (int i = 0; i < n; i++)
        cin >> v[i];
}
 
template<typename T>
vector<T> UNQ(vector<T> a) {
    vector<T> ans;
    for (T t: a)
        if (ans.empty() || t != ans.back())
            ans.push_back(t);
    return ans;
}
 
ll ceil(ll a, ll b) {
    ll ans = a / b;
    if (a % b)ans++;
    return ans;
}
 
ld log(ld a, ld b) { return log(b) / log(a); }
 
ll power(ll base, ll exp, ll M = 1e18) {//(base^exp)%M
    ll ans = 1;
    while (exp) {
        if (exp % 2 == 1)ans = ((ans % M) * (base % M)) % M;
        base = ((base % M) * (base % M)) % M;
        exp /= 2;
    }
    return ans;
}
 
string to_base(int n, int new_base) {
    string s;
    int nn = n;
    while (nn) {
        s += to_string(nn % new_base);
        nn /= new_base;
    }
    reverse(all(s));
    return s;
}
 
ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);
    if (b == 0)return a;
    return gcd(b, a % b);
}
 
ll lcm(ll a, ll b) {
    ll x = (a / gcd(a, b));
    return b * x;
}
 
vl generate_array(ll n, ll mn = 1, ll mx = 1e18 + 1) {
    if (mx == 1e18 + 1)
        mx = n;
    vl ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = (mn + rand() % (mx - mn + 1));
    return ans;
}
 
string substr(string s, int l, int r) {
    string ans;
    for (int i = l; i <= r; i++)
        ans += s[i];
    return ans;
}
 
int query(string);
 
vi cnt;
 
string merge(string s,string t){
    if(s.size()<t.size())
        swap(s,t);
    for(int i=-1; i<int(s.size()); i++){
        if(!t.size())break;
        string cur=s.substr(0,i+1)+string(1,t[0])+s.substr(i+1,s.size()-(i+1));
        if(query(cur)==cur.size()){
            s=s.substr(0,i+1)+string(1,t[0])+s.substr(i+1,s.size()-(i+1));
            t=t.substr(1,t.size()-1);
        }
    }
    return s;
}
string dfs(int l,int r,int n){
    if(l>r)return "";
    else if(l==r)return string(cnt[l],l+'a');
 
    int m=(l+r)/2;
    return merge(dfs(l,m,n),dfs(m+1,r,n));
}
string guess(int n,int AB){
    cnt=vi(26);
    int sum=0;
    for(int i=0; i<AB; i++){
        int ans=query(string(n,i+'a'));
        cnt[i]=ans;
        sum+=ans;
    }
    return dfs(0,AB-1,n);
}

Compilation message

password.cpp: In function 'std::string merge(std::string, std::string)':
password.cpp:143:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         if(query(cur)==cur.size()){
      |            ~~~~~~~~~~^~~~~~~~~~~~
password.cpp: In function 'void usaco(std::string)':
password.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
password.cpp:58:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 68 queries.
2 Correct 2 ms 200 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 280 KB Guessed the password with 52 queries.
2 Correct 2 ms 200 KB Guessed the password with 116 queries.
3 Correct 1 ms 296 KB Guessed the password with 105 queries.
4 Correct 2 ms 200 KB Guessed the password with 199 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 368 KB Guessed the password with 3462 queries.
2 Correct 56 ms 384 KB Guessed the password with 5035 queries.
3 Correct 44 ms 320 KB Guessed the password with 6355 queries.
4 Correct 73 ms 440 KB Guessed the password with 8715 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 68 queries.
2 Correct 2 ms 200 KB Guessed the password with 111 queries.
3 Correct 1 ms 280 KB Guessed the password with 52 queries.
4 Correct 2 ms 200 KB Guessed the password with 116 queries.
5 Correct 1 ms 296 KB Guessed the password with 105 queries.
6 Correct 2 ms 200 KB Guessed the password with 199 queries.
7 Correct 16 ms 368 KB Guessed the password with 3462 queries.
8 Correct 56 ms 384 KB Guessed the password with 5035 queries.
9 Correct 44 ms 320 KB Guessed the password with 6355 queries.
10 Correct 73 ms 440 KB Guessed the password with 8715 queries.
11 Correct 120 ms 512 KB Guessed the password with 13650 queries.
12 Correct 125 ms 388 KB Guessed the password with 12460 queries.
13 Correct 89 ms 508 KB Guessed the password with 14407 queries.
14 Correct 112 ms 392 KB Guessed the password with 13973 queries.
15 Correct 153 ms 552 KB Guessed the password with 15077 queries.
16 Correct 86 ms 504 KB Guessed the password with 14160 queries.
17 Correct 155 ms 436 KB Guessed the password with 16061 queries.
18 Correct 104 ms 624 KB Guessed the password with 15212 queries.
19 Correct 123 ms 536 KB Guessed the password with 16417 queries.
20 Correct 156 ms 516 KB Guessed the password with 14253 queries.
21 Correct 163 ms 456 KB Guessed the password with 16875 queries.
22 Correct 164 ms 476 KB Guessed the password with 15478 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 68 queries.
2 Correct 2 ms 200 KB Guessed the password with 111 queries.
3 Correct 1 ms 280 KB Guessed the password with 52 queries.
4 Correct 2 ms 200 KB Guessed the password with 116 queries.
5 Correct 1 ms 296 KB Guessed the password with 105 queries.
6 Correct 2 ms 200 KB Guessed the password with 199 queries.
7 Correct 16 ms 368 KB Guessed the password with 3462 queries.
8 Correct 56 ms 384 KB Guessed the password with 5035 queries.
9 Correct 44 ms 320 KB Guessed the password with 6355 queries.
10 Correct 73 ms 440 KB Guessed the password with 8715 queries.
11 Correct 120 ms 512 KB Guessed the password with 13650 queries.
12 Correct 125 ms 388 KB Guessed the password with 12460 queries.
13 Correct 89 ms 508 KB Guessed the password with 14407 queries.
14 Correct 112 ms 392 KB Guessed the password with 13973 queries.
15 Correct 153 ms 552 KB Guessed the password with 15077 queries.
16 Correct 86 ms 504 KB Guessed the password with 14160 queries.
17 Correct 155 ms 436 KB Guessed the password with 16061 queries.
18 Correct 104 ms 624 KB Guessed the password with 15212 queries.
19 Correct 123 ms 536 KB Guessed the password with 16417 queries.
20 Correct 156 ms 516 KB Guessed the password with 14253 queries.
21 Correct 163 ms 456 KB Guessed the password with 16875 queries.
22 Correct 164 ms 476 KB Guessed the password with 15478 queries.
23 Correct 276 ms 536 KB Guessed the password with 23705 queries.
24 Correct 230 ms 468 KB Guessed the password with 22240 queries.
25 Correct 225 ms 452 KB Guessed the password with 23865 queries.
26 Correct 300 ms 584 KB Guessed the password with 23349 queries.
27 Correct 251 ms 608 KB Guessed the password with 23792 queries.
28 Correct 250 ms 452 KB Guessed the password with 23049 queries.
29 Correct 237 ms 660 KB Guessed the password with 23871 queries.
30 Correct 204 ms 436 KB Guessed the password with 22509 queries.