oj.uz

Submission #333453

# Submission time Handle Problem Language Result Execution time Memory
333453 2020-12-06T04:51:48 Z ijxjdjd Password (RMI18_password) C++14
100 / 100
 427 ms 876 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;

typedef pair<int, int> pi;
typedef  pair<long, long> pl;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;


#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FR(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define RF(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
//string ori;
//int query(str s) {
//    int cur = 0;
//    for (int i = 0; i < ori.length() && cur < s.length(); i++) {
//        if (ori[i] == s[cur]) {
//            cur++;
//        }
//    }
//    return cur;
//}
int query(string str);
string guess(int n, int s) {
    vector<str> vec(s);
    FR(i, s) {
        str base = "";
        FR(j, n) {
            base += (char)(i + 'a');
        }
        vec[i] = base.substr(0, query(base));
    }
    sort(vec.begin(), vec.end(), [ ](const string& lhs, const string& rhs){
            return (lhs.length() < rhs.length());
        });
    string cur = "";
    RF(i, s) {
        string next = vec[i];
        FR(j, vec[i].length()) {
            int low = 0;
            int high = cur.length();
            while (low < high) {
                int mid = (low + high + 1)/2;
                string cpy = vec[i];
                cpy.insert(j, cur.substr(0, mid));
                if (query(cpy) == cpy.length()) {
                    low = mid;
                }
                else {
                    high = mid-1;
                }
            }
            vec[i].insert(j, cur.substr(0, low));
            cur = cur.substr(low);
            j += low;
        }
        vec[i] += cur;
        cur = vec[i];
    }
    return cur;
}

//int main() {
//    ios_base::sync_with_stdio(false);
//    cin.tie(0);
//    cin >> ori;
//    cout << guess(ori.size(), 26) << endl;
//}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:17:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
password.cpp:18:17: note: in expansion of macro 'FOR'
   18 | #define FR(i,a) FOR(i,0,a)
      |                 ^~~
password.cpp:48:9: note: in expansion of macro 'FR'
   48 |         FR(j, vec[i].length()) {
      |         ^~
password.cpp:55:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                 if (query(cpy) == cpy.length()) {
      |                     ~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 57 queries.
2 Correct 1 ms 384 KB Guessed the password with 99 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Guessed the password with 52 queries.
2 Correct 2 ms 384 KB Guessed the password with 105 queries.
3 Correct 1 ms 364 KB Guessed the password with 17 queries.
4 Correct 4 ms 364 KB Guessed the password with 270 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 512 KB Guessed the password with 6010 queries.
2 Correct 56 ms 416 KB Guessed the password with 7985 queries.
3 Correct 96 ms 620 KB Guessed the password with 9961 queries.
4 Correct 148 ms 620 KB Guessed the password with 14746 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 57 queries.
2 Correct 1 ms 384 KB Guessed the password with 99 queries.
3 Correct 1 ms 376 KB Guessed the password with 52 queries.
4 Correct 2 ms 384 KB Guessed the password with 105 queries.
5 Correct 1 ms 364 KB Guessed the password with 17 queries.
6 Correct 4 ms 364 KB Guessed the password with 270 queries.
7 Correct 63 ms 512 KB Guessed the password with 6010 queries.
8 Correct 56 ms 416 KB Guessed the password with 7985 queries.
9 Correct 96 ms 620 KB Guessed the password with 9961 queries.
10 Correct 148 ms 620 KB Guessed the password with 14746 queries.
11 Correct 163 ms 784 KB Guessed the password with 19184 queries.
12 Correct 197 ms 432 KB Guessed the password with 19154 queries.
13 Correct 206 ms 740 KB Guessed the password with 22619 queries.
14 Correct 263 ms 620 KB Guessed the password with 23377 queries.
15 Correct 210 ms 820 KB Guessed the password with 24624 queries.
16 Correct 251 ms 552 KB Guessed the password with 23727 queries.
17 Correct 248 ms 704 KB Guessed the password with 24701 queries.
18 Correct 234 ms 600 KB Guessed the password with 23563 queries.
19 Correct 251 ms 828 KB Guessed the password with 23651 queries.
20 Correct 301 ms 596 KB Guessed the password with 23939 queries.
21 Correct 267 ms 728 KB Guessed the password with 25361 queries.
22 Correct 188 ms 876 KB Guessed the password with 21188 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 57 queries.
2 Correct 1 ms 384 KB Guessed the password with 99 queries.
3 Correct 1 ms 376 KB Guessed the password with 52 queries.
4 Correct 2 ms 384 KB Guessed the password with 105 queries.
5 Correct 1 ms 364 KB Guessed the password with 17 queries.
6 Correct 4 ms 364 KB Guessed the password with 270 queries.
7 Correct 63 ms 512 KB Guessed the password with 6010 queries.
8 Correct 56 ms 416 KB Guessed the password with 7985 queries.
9 Correct 96 ms 620 KB Guessed the password with 9961 queries.
10 Correct 148 ms 620 KB Guessed the password with 14746 queries.
11 Correct 163 ms 784 KB Guessed the password with 19184 queries.
12 Correct 197 ms 432 KB Guessed the password with 19154 queries.
13 Correct 206 ms 740 KB Guessed the password with 22619 queries.
14 Correct 263 ms 620 KB Guessed the password with 23377 queries.
15 Correct 210 ms 820 KB Guessed the password with 24624 queries.
16 Correct 251 ms 552 KB Guessed the password with 23727 queries.
17 Correct 248 ms 704 KB Guessed the password with 24701 queries.
18 Correct 234 ms 600 KB Guessed the password with 23563 queries.
19 Correct 251 ms 828 KB Guessed the password with 23651 queries.
20 Correct 301 ms 596 KB Guessed the password with 23939 queries.
21 Correct 267 ms 728 KB Guessed the password with 25361 queries.
22 Correct 188 ms 876 KB Guessed the password with 21188 queries.
23 Correct 405 ms 844 KB Guessed the password with 45544 queries.
24 Correct 362 ms 720 KB Guessed the password with 42658 queries.
25 Correct 427 ms 624 KB Guessed the password with 45816 queries.
26 Correct 317 ms 704 KB Guessed the password with 40412 queries.
27 Correct 386 ms 700 KB Guessed the password with 45449 queries.
28 Correct 367 ms 672 KB Guessed the password with 41662 queries.
29 Correct 377 ms 640 KB Guessed the password with 45352 queries.
30 Correct 339 ms 772 KB Guessed the password with 37400 queries.