oj.uz

Submission #218153

# Submission time Handle Problem Language Result Execution time Memory
218153 2020-04-01T10:33:54 Z 2fat2code Password (RMI18_password) C++17
100 / 100
 268 ms 760 KB 
#include <bits/stdc++.h>
//#include "victor.h"
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz() size()
#define fr first
#define sc second
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int mod=1e9+7;
const int modp=1999999973;
const int modulo=998244353;

int cnt[26];
queue<string>q;

int query(string str);

string guess(int n,int s){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    for(int i=0;i<s;i++){
        string tz;
        for(int j=1;j<=n;j++) tz.push_back(i+'a');
        cnt[i] = query(tz);
    }
    for(int i=0;i<s;i++){
        string tz;
        for(int j=1;j<=cnt[i];j++) tz.push_back(i+'a');
        if(tz.size()) q.push(tz);
    }
    while(q.size()>=2){
        string t1=q.front();
        q.pop();
        string t2=q.front();
        q.pop();
        string pref="";
        int i=0;
        for(int j=0;j<=t2.size();j++){
            string t4 = pref + t1[i] + t2.substr(j,t2.size()-j);
            if(query(t4)==(t2.size()+i+1)){
                pref.push_back(t1[i]);
                i++;
                if(i==t1.size()){
                    pref+=t2.substr(j,t2.size()-j);
                    break;
                }
                j--;
            }
            else pref.push_back(t2[j]);
        }
        q.push(pref);
    }
    return q.front();
}

Compilation message

password.cpp: In function 'std::__cxx11::string guess(int, int)':
password.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<=t2.size();j++){
                     ~^~~~~~~~~~~
password.cpp:51:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(query(t4)==(t2.size()+i+1)){
                ~~~~~~~~~^~~~~~~~~~~~~~~~~
password.cpp:54:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(i==t1.size()){
                    ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 69 queries.
2 Correct 7 ms 384 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 52 queries.
2 Correct 6 ms 384 KB Guessed the password with 119 queries.
3 Correct 5 ms 384 KB Guessed the password with 91 queries.
4 Correct 5 ms 396 KB Guessed the password with 198 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 384 KB Guessed the password with 3525 queries.
2 Correct 54 ms 400 KB Guessed the password with 5054 queries.
3 Correct 70 ms 384 KB Guessed the password with 6642 queries.
4 Correct 89 ms 504 KB Guessed the password with 8854 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 69 queries.
2 Correct 7 ms 384 KB Guessed the password with 111 queries.
3 Correct 5 ms 384 KB Guessed the password with 52 queries.
4 Correct 6 ms 384 KB Guessed the password with 119 queries.
5 Correct 5 ms 384 KB Guessed the password with 91 queries.
6 Correct 5 ms 396 KB Guessed the password with 198 queries.
7 Correct 39 ms 384 KB Guessed the password with 3525 queries.
8 Correct 54 ms 400 KB Guessed the password with 5054 queries.
9 Correct 70 ms 384 KB Guessed the password with 6642 queries.
10 Correct 89 ms 504 KB Guessed the password with 8854 queries.
11 Correct 141 ms 504 KB Guessed the password with 13693 queries.
12 Correct 89 ms 400 KB Guessed the password with 11613 queries.
13 Correct 142 ms 504 KB Guessed the password with 14467 queries.
14 Correct 122 ms 384 KB Guessed the password with 13173 queries.
15 Correct 148 ms 384 KB Guessed the password with 15283 queries.
16 Correct 134 ms 504 KB Guessed the password with 13581 queries.
17 Correct 164 ms 480 KB Guessed the password with 15383 queries.
18 Correct 133 ms 504 KB Guessed the password with 13390 queries.
19 Correct 155 ms 760 KB Guessed the password with 14998 queries.
20 Correct 135 ms 384 KB Guessed the password with 13430 queries.
21 Correct 169 ms 632 KB Guessed the password with 17272 queries.
22 Correct 144 ms 504 KB Guessed the password with 14054 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 69 queries.
2 Correct 7 ms 384 KB Guessed the password with 111 queries.
3 Correct 5 ms 384 KB Guessed the password with 52 queries.
4 Correct 6 ms 384 KB Guessed the password with 119 queries.
5 Correct 5 ms 384 KB Guessed the password with 91 queries.
6 Correct 5 ms 396 KB Guessed the password with 198 queries.
7 Correct 39 ms 384 KB Guessed the password with 3525 queries.
8 Correct 54 ms 400 KB Guessed the password with 5054 queries.
9 Correct 70 ms 384 KB Guessed the password with 6642 queries.
10 Correct 89 ms 504 KB Guessed the password with 8854 queries.
11 Correct 141 ms 504 KB Guessed the password with 13693 queries.
12 Correct 89 ms 400 KB Guessed the password with 11613 queries.
13 Correct 142 ms 504 KB Guessed the password with 14467 queries.
14 Correct 122 ms 384 KB Guessed the password with 13173 queries.
15 Correct 148 ms 384 KB Guessed the password with 15283 queries.
16 Correct 134 ms 504 KB Guessed the password with 13581 queries.
17 Correct 164 ms 480 KB Guessed the password with 15383 queries.
18 Correct 133 ms 504 KB Guessed the password with 13390 queries.
19 Correct 155 ms 760 KB Guessed the password with 14998 queries.
20 Correct 135 ms 384 KB Guessed the password with 13430 queries.
21 Correct 169 ms 632 KB Guessed the password with 17272 queries.
22 Correct 144 ms 504 KB Guessed the password with 14054 queries.
23 Correct 246 ms 480 KB Guessed the password with 23785 queries.
24 Correct 215 ms 536 KB Guessed the password with 23147 queries.
25 Correct 234 ms 540 KB Guessed the password with 23746 queries.
26 Correct 268 ms 728 KB Guessed the password with 23995 queries.
27 Correct 247 ms 620 KB Guessed the password with 23803 queries.
28 Correct 222 ms 664 KB Guessed the password with 24040 queries.
29 Correct 254 ms 652 KB Guessed the password with 23821 queries.
30 Correct 233 ms 696 KB Guessed the password with 22860 queries.