oj.uz

Submission #492835

# Submission time Handle Problem Language Result Execution time Memory
492835 2021-12-09T07:17:46 Z Carmel_Ab1 Password (RMI18_password) C++17
100 / 100
 265 ms 776 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){
    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:141:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         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 2 ms 200 KB Guessed the password with 98 queries.
2 Correct 2 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 57 queries.
2 Correct 1 ms 200 KB Guessed the password with 129 queries.
3 Correct 2 ms 200 KB Guessed the password with 110 queries.
4 Correct 2 ms 296 KB Guessed the password with 225 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 448 KB Guessed the password with 3804 queries.
2 Correct 55 ms 380 KB Guessed the password with 5174 queries.
3 Correct 63 ms 396 KB Guessed the password with 6737 queries.
4 Correct 101 ms 432 KB Guessed the password with 8901 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 98 queries.
2 Correct 2 ms 200 KB Guessed the password with 166 queries.
3 Correct 1 ms 200 KB Guessed the password with 57 queries.
4 Correct 1 ms 200 KB Guessed the password with 129 queries.
5 Correct 2 ms 200 KB Guessed the password with 110 queries.
6 Correct 2 ms 296 KB Guessed the password with 225 queries.
7 Correct 34 ms 448 KB Guessed the password with 3804 queries.
8 Correct 55 ms 380 KB Guessed the password with 5174 queries.
9 Correct 63 ms 396 KB Guessed the password with 6737 queries.
10 Correct 101 ms 432 KB Guessed the password with 8901 queries.
11 Correct 137 ms 436 KB Guessed the password with 13872 queries.
12 Correct 162 ms 308 KB Guessed the password with 12914 queries.
13 Correct 141 ms 528 KB Guessed the password with 14629 queries.
14 Correct 97 ms 580 KB Guessed the password with 14240 queries.
15 Correct 146 ms 520 KB Guessed the password with 15537 queries.
16 Correct 79 ms 532 KB Guessed the password with 14749 queries.
17 Correct 175 ms 432 KB Guessed the password with 16271 queries.
18 Correct 178 ms 488 KB Guessed the password with 15566 queries.
19 Correct 245 ms 528 KB Guessed the password with 16637 queries.
20 Correct 181 ms 520 KB Guessed the password with 15358 queries.
21 Correct 191 ms 528 KB Guessed the password with 17182 queries.
22 Correct 205 ms 380 KB Guessed the password with 16183 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 98 queries.
2 Correct 2 ms 200 KB Guessed the password with 166 queries.
3 Correct 1 ms 200 KB Guessed the password with 57 queries.
4 Correct 1 ms 200 KB Guessed the password with 129 queries.
5 Correct 2 ms 200 KB Guessed the password with 110 queries.
6 Correct 2 ms 296 KB Guessed the password with 225 queries.
7 Correct 34 ms 448 KB Guessed the password with 3804 queries.
8 Correct 55 ms 380 KB Guessed the password with 5174 queries.
9 Correct 63 ms 396 KB Guessed the password with 6737 queries.
10 Correct 101 ms 432 KB Guessed the password with 8901 queries.
11 Correct 137 ms 436 KB Guessed the password with 13872 queries.
12 Correct 162 ms 308 KB Guessed the password with 12914 queries.
13 Correct 141 ms 528 KB Guessed the password with 14629 queries.
14 Correct 97 ms 580 KB Guessed the password with 14240 queries.
15 Correct 146 ms 520 KB Guessed the password with 15537 queries.
16 Correct 79 ms 532 KB Guessed the password with 14749 queries.
17 Correct 175 ms 432 KB Guessed the password with 16271 queries.
18 Correct 178 ms 488 KB Guessed the password with 15566 queries.
19 Correct 245 ms 528 KB Guessed the password with 16637 queries.
20 Correct 181 ms 520 KB Guessed the password with 15358 queries.
21 Correct 191 ms 528 KB Guessed the password with 17182 queries.
22 Correct 205 ms 380 KB Guessed the password with 16183 queries.
23 Correct 222 ms 652 KB Guessed the password with 23971 queries.
24 Correct 206 ms 544 KB Guessed the password with 23040 queries.
25 Correct 253 ms 668 KB Guessed the password with 24113 queries.
26 Correct 265 ms 500 KB Guessed the password with 23605 queries.
27 Correct 257 ms 656 KB Guessed the password with 24069 queries.
28 Correct 153 ms 632 KB Guessed the password with 23672 queries.
29 Correct 263 ms 644 KB Guessed the password with 24135 queries.
30 Correct 251 ms 776 KB Guessed the password with 24065 queries.