oj.uz

Submission #492770

# Submission time Handle Problem Language Result Execution time Memory
492770 2021-12-08T20:58:37 Z Carmel_Ab1 Password (RMI18_password) C++17
50 / 100
 496 ms 600 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);

string guess(int n,int AB){
    vi cnt(26);

    int sum=0;
    for(int i=0; i<26; 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;
    }

    string ans;
    int mx=0;
    for(int i=0; i<26; i++)
        if(cnt[i]>ans.size())
            ans=string(cnt[i],i+'a'),mx=i;

    for(int i=0; i<26; i++){
        if(i==mx || !cnt[i])
            continue;
        string s=string(cnt[i],i+'a');

        for(int j=-1; j<=int(ans.size()); j++){
            if(!s.size())break;
            if(ans.size()+1!=query(ans.substr(0,j+1)+string(1,i+'a')+ans.substr(j+1,ans.size()-(j+1))))
                continue;
            ans=ans.substr(0,j+1)+string(1,i+'a')+ans.substr(j+1,ans.size()-(j+1));
            s.pop_back();
        }
    }
    return ans;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:155:18: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         if(cnt[i]>ans.size())
password.cpp:165:28: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  165 |             if(ans.size()+1!=query(ans.substr(0,j+1)+string(1,i+'a')+ans.substr(j+1,ans.size()-(j+1))))
      |                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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 106 queries.
2 Correct 2 ms 200 KB Guessed the password with 242 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 2 ms 200 KB Guessed the password with 198 queries.
4 Correct 3 ms 200 KB Guessed the password with 238 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 348 KB Guessed the password with 4888 queries.
2 Correct 99 ms 348 KB Guessed the password with 10402 queries.
3 Correct 141 ms 436 KB Guessed the password with 13820 queries.
4 Correct 222 ms 444 KB Guessed the password with 20869 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 106 queries.
2 Correct 2 ms 200 KB Guessed the password with 242 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 2 ms 200 KB Guessed the password with 198 queries.
6 Correct 3 ms 200 KB Guessed the password with 238 queries.
7 Correct 56 ms 348 KB Guessed the password with 4888 queries.
8 Correct 99 ms 348 KB Guessed the password with 10402 queries.
9 Correct 141 ms 436 KB Guessed the password with 13820 queries.
10 Correct 222 ms 444 KB Guessed the password with 20869 queries.
11 Correct 453 ms 548 KB Guessed the password with 49702 queries.
12 Correct 166 ms 472 KB Guessed the password with 19417 queries.
13 Correct 427 ms 476 KB Guessed the password with 47902 queries.
14 Correct 259 ms 480 KB Guessed the password with 26587 queries.
15 Correct 363 ms 600 KB Guessed the password with 45059 queries.
16 Correct 148 ms 364 KB Guessed the password with 24600 queries.
17 Correct 496 ms 348 KB Guessed the password with 49951 queries.
18 Correct 232 ms 464 KB Guessed the password with 25049 queries.
19 Incorrect 328 ms 336 KB Could not guess the password with 50000 queries.
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 106 queries.
2 Correct 2 ms 200 KB Guessed the password with 242 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 2 ms 200 KB Guessed the password with 198 queries.
6 Correct 3 ms 200 KB Guessed the password with 238 queries.
7 Correct 56 ms 348 KB Guessed the password with 4888 queries.
8 Correct 99 ms 348 KB Guessed the password with 10402 queries.
9 Correct 141 ms 436 KB Guessed the password with 13820 queries.
10 Correct 222 ms 444 KB Guessed the password with 20869 queries.
11 Correct 453 ms 548 KB Guessed the password with 49702 queries.
12 Correct 166 ms 472 KB Guessed the password with 19417 queries.
13 Correct 427 ms 476 KB Guessed the password with 47902 queries.
14 Correct 259 ms 480 KB Guessed the password with 26587 queries.
15 Correct 363 ms 600 KB Guessed the password with 45059 queries.
16 Correct 148 ms 364 KB Guessed the password with 24600 queries.
17 Correct 496 ms 348 KB Guessed the password with 49951 queries.
18 Correct 232 ms 464 KB Guessed the password with 25049 queries.
19 Incorrect 328 ms 336 KB Could not guess the password with 50000 queries.
20 Halted 0 ms 0 KB -