oj.uz

답안 #503280

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503280 2022-01-07T15:29:02 Z Carmel_Ab1 Password (RMI18_password) C++17
50 / 100
 172 ms 448 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 280 KB Guessed the password with 68 queries.
2 Correct 2 ms 284 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Guessed the password with 52 queries.
2 Correct 2 ms 264 KB Guessed the password with 116 queries.
3 Correct 1 ms 200 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

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 296 KB Guessed the password with 3462 queries.
2 Correct 44 ms 384 KB Guessed the password with 5035 queries.
3 Correct 68 ms 448 KB Guessed the password with 6355 queries.
4 Correct 102 ms 392 KB Guessed the password with 8715 queries.

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 280 KB Guessed the password with 68 queries.
2 Correct 2 ms 284 KB Guessed the password with 111 queries.
3 Correct 0 ms 200 KB Guessed the password with 52 queries.
4 Correct 2 ms 264 KB Guessed the password with 116 queries.
5 Correct 1 ms 200 KB Guessed the password with 105 queries.
6 Correct 2 ms 200 KB Guessed the password with 199 queries.
7 Correct 40 ms 296 KB Guessed the password with 3462 queries.
8 Correct 44 ms 384 KB Guessed the password with 5035 queries.
9 Correct 68 ms 448 KB Guessed the password with 6355 queries.
10 Correct 102 ms 392 KB Guessed the password with 8715 queries.
11 Correct 154 ms 388 KB Guessed the password with 13650 queries.
12 Correct 150 ms 376 KB Guessed the password with 12460 queries.
13 Runtime error 172 ms 396 KB Execution killed with signal 13
14 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 280 KB Guessed the password with 68 queries.
2 Correct 2 ms 284 KB Guessed the password with 111 queries.
3 Correct 0 ms 200 KB Guessed the password with 52 queries.
4 Correct 2 ms 264 KB Guessed the password with 116 queries.
5 Correct 1 ms 200 KB Guessed the password with 105 queries.
6 Correct 2 ms 200 KB Guessed the password with 199 queries.
7 Correct 40 ms 296 KB Guessed the password with 3462 queries.
8 Correct 44 ms 384 KB Guessed the password with 5035 queries.
9 Correct 68 ms 448 KB Guessed the password with 6355 queries.
10 Correct 102 ms 392 KB Guessed the password with 8715 queries.
11 Correct 154 ms 388 KB Guessed the password with 13650 queries.
12 Correct 150 ms 376 KB Guessed the password with 12460 queries.
13 Runtime error 172 ms 396 KB Execution killed with signal 13
14 Halted 0 ms 0 KB -