oj.uz

Submission #492836

# Submission time Handle Problem Language Result Execution time Memory
492836 2021-12-09T07:19:32 Z Carmel_Ab1 Password (RMI18_password) C++17
100 / 100
 299 ms 756 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 l=1,r=n-sum,ans=0;
        while(l<=r){
            int m=(l+r)/2;
            if(query(string(m,('a'+i)))==m)
                ans=m,l=m+1;
            else
                r=m-1;
        }
        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 98 queries.
2 Correct 3 ms 200 KB Guessed the password with 166 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 61 queries.
2 Correct 2 ms 200 KB Guessed the password with 129 queries.
3 Correct 3 ms 200 KB Guessed the password with 122 queries.
4 Correct 3 ms 292 KB Guessed the password with 221 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 384 KB Guessed the password with 3562 queries.
2 Correct 63 ms 364 KB Guessed the password with 5156 queries.
3 Correct 76 ms 300 KB Guessed the password with 6508 queries.
4 Correct 97 ms 440 KB Guessed the password with 8895 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 98 queries.
2 Correct 3 ms 200 KB Guessed the password with 166 queries.
3 Correct 1 ms 200 KB Guessed the password with 61 queries.
4 Correct 2 ms 200 KB Guessed the password with 129 queries.
5 Correct 3 ms 200 KB Guessed the password with 122 queries.
6 Correct 3 ms 292 KB Guessed the password with 221 queries.
7 Correct 35 ms 384 KB Guessed the password with 3562 queries.
8 Correct 63 ms 364 KB Guessed the password with 5156 queries.
9 Correct 76 ms 300 KB Guessed the password with 6508 queries.
10 Correct 97 ms 440 KB Guessed the password with 8895 queries.
11 Correct 155 ms 516 KB Guessed the password with 13840 queries.
12 Correct 138 ms 508 KB Guessed the password with 12720 queries.
13 Correct 149 ms 388 KB Guessed the password with 14626 queries.
14 Correct 137 ms 380 KB Guessed the password with 14234 queries.
15 Correct 132 ms 520 KB Guessed the password with 15300 queries.
16 Correct 133 ms 756 KB Guessed the password with 14424 queries.
17 Correct 180 ms 456 KB Guessed the password with 16218 queries.
18 Correct 166 ms 404 KB Guessed the password with 15484 queries.
19 Correct 121 ms 424 KB Guessed the password with 16569 queries.
20 Correct 166 ms 460 KB Guessed the password with 14523 queries.
21 Correct 194 ms 372 KB Guessed the password with 17067 queries.
22 Correct 170 ms 436 KB Guessed the password with 15753 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 98 queries.
2 Correct 3 ms 200 KB Guessed the password with 166 queries.
3 Correct 1 ms 200 KB Guessed the password with 61 queries.
4 Correct 2 ms 200 KB Guessed the password with 129 queries.
5 Correct 3 ms 200 KB Guessed the password with 122 queries.
6 Correct 3 ms 292 KB Guessed the password with 221 queries.
7 Correct 35 ms 384 KB Guessed the password with 3562 queries.
8 Correct 63 ms 364 KB Guessed the password with 5156 queries.
9 Correct 76 ms 300 KB Guessed the password with 6508 queries.
10 Correct 97 ms 440 KB Guessed the password with 8895 queries.
11 Correct 155 ms 516 KB Guessed the password with 13840 queries.
12 Correct 138 ms 508 KB Guessed the password with 12720 queries.
13 Correct 149 ms 388 KB Guessed the password with 14626 queries.
14 Correct 137 ms 380 KB Guessed the password with 14234 queries.
15 Correct 132 ms 520 KB Guessed the password with 15300 queries.
16 Correct 133 ms 756 KB Guessed the password with 14424 queries.
17 Correct 180 ms 456 KB Guessed the password with 16218 queries.
18 Correct 166 ms 404 KB Guessed the password with 15484 queries.
19 Correct 121 ms 424 KB Guessed the password with 16569 queries.
20 Correct 166 ms 460 KB Guessed the password with 14523 queries.
21 Correct 194 ms 372 KB Guessed the password with 17067 queries.
22 Correct 170 ms 436 KB Guessed the password with 15753 queries.
23 Correct 262 ms 612 KB Guessed the password with 23968 queries.
24 Correct 262 ms 536 KB Guessed the password with 22510 queries.
25 Correct 274 ms 672 KB Guessed the password with 24125 queries.
26 Correct 277 ms 680 KB Guessed the password with 23580 queries.
27 Correct 299 ms 540 KB Guessed the password with 24054 queries.
28 Correct 193 ms 604 KB Guessed the password with 23285 queries.
29 Correct 263 ms 416 KB Guessed the password with 24133 queries.
30 Correct 222 ms 512 KB Guessed the password with 22756 queries.