oj.uz

답안 #492771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
492771 2021-12-08T21:13:15 Z Carmel_Ab1 Password (RMI18_password) C++17
50 / 100
 525 ms 480 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<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;
    }

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 336 KB Guessed the password with 4888 queries.
2 Correct 113 ms 340 KB Guessed the password with 10402 queries.
3 Correct 150 ms 400 KB Guessed the password with 13820 queries.
4 Correct 184 ms 468 KB Guessed the password with 20869 queries.

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 72 ms 336 KB Guessed the password with 4888 queries.
8 Correct 113 ms 340 KB Guessed the password with 10402 queries.
9 Correct 150 ms 400 KB Guessed the password with 13820 queries.
10 Correct 184 ms 468 KB Guessed the password with 20869 queries.
11 Correct 525 ms 348 KB Guessed the password with 49702 queries.
12 Correct 207 ms 352 KB Guessed the password with 19417 queries.
13 Correct 508 ms 480 KB Guessed the password with 47902 queries.
14 Correct 272 ms 472 KB Guessed the password with 26587 queries.
15 Correct 429 ms 480 KB Guessed the password with 45059 queries.
16 Correct 205 ms 456 KB Guessed the password with 24600 queries.
17 Correct 392 ms 332 KB Guessed the password with 49951 queries.
18 Correct 173 ms 472 KB Guessed the password with 25049 queries.
19 Incorrect 362 ms 340 KB Could not guess the password with 50000 queries.
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 72 ms 336 KB Guessed the password with 4888 queries.
8 Correct 113 ms 340 KB Guessed the password with 10402 queries.
9 Correct 150 ms 400 KB Guessed the password with 13820 queries.
10 Correct 184 ms 468 KB Guessed the password with 20869 queries.
11 Correct 525 ms 348 KB Guessed the password with 49702 queries.
12 Correct 207 ms 352 KB Guessed the password with 19417 queries.
13 Correct 508 ms 480 KB Guessed the password with 47902 queries.
14 Correct 272 ms 472 KB Guessed the password with 26587 queries.
15 Correct 429 ms 480 KB Guessed the password with 45059 queries.
16 Correct 205 ms 456 KB Guessed the password with 24600 queries.
17 Correct 392 ms 332 KB Guessed the password with 49951 queries.
18 Correct 173 ms 472 KB Guessed the password with 25049 queries.
19 Incorrect 362 ms 340 KB Could not guess the password with 50000 queries.
20 Halted 0 ms 0 KB -