oj.uz

Submission #201352

# Submission time Handle Problem Language Result Execution time Memory
201352 2020-02-10T09:59:10 Z theStaticMind Password (RMI18_password) C++14
100 / 100
 259 ms 700 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int, int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;
int query(string s);
string merge(string a, string b){
      int j = 0;
      if(a.length() > b.length())swap(a, b);
      for(int i = 0; i <= a.length() && j < b.length(); i++){
            string w = a;
            string::iterator itr = a.insert(a.begin() + i, b[j]);
            if(query(a) == a.length()){
                  j++;
            }
            else {
                  a.erase(itr);
            }
      }
      return a;
}
string guess(int n, int k){
      vector<string> seg;
      for(int i = 0; i < k; i++){
            string s;
            for(int j = 0; j < n; j++) s.pb('a' + i);
            int l = query(s);
            s.clear();
            for(int j = 0; j < l; j++) s.pb('a' + i);
            seg.pb(s);
      }
      while(seg.size() != 1){
            vector<string> temp;
            for(int i = 1; i < seg.size(); i += 2){
                  temp.pb(merge(seg[i - 1], seg[i]));
            }
            if(seg.size() % 2)temp.pb(seg.back());
            swap(temp, seg);
      }
      return seg[0];
}

Compilation message

password.cpp: In function 'std::__cxx11::string merge(std::__cxx11::string, std::__cxx11::string)':
password.cpp:14:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i <= a.length() && j < b.length(); i++){
                      ~~^~~~~~~~~~~~~
password.cpp:14:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i <= a.length() && j < b.length(); i++){
                                         ~~^~~~~~~~~~~~
password.cpp:17:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(query(a) == a.length()){
                ~~~~~~~~~^~~~~~~~~~~~~
password.cpp: In function 'std::__cxx11::string guess(int, int)':
password.cpp:38:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 1; i < seg.size(); i += 2){
                            ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Guessed the password with 67 queries.
2 Correct 6 ms 248 KB Guessed the password with 118 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Guessed the password with 48 queries.
2 Correct 5 ms 376 KB Guessed the password with 127 queries.
3 Correct 6 ms 248 KB Guessed the password with 91 queries.
4 Correct 6 ms 376 KB Guessed the password with 202 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 252 KB Guessed the password with 3605 queries.
2 Correct 50 ms 248 KB Guessed the password with 5123 queries.
3 Correct 70 ms 248 KB Guessed the password with 7162 queries.
4 Correct 94 ms 376 KB Guessed the password with 9144 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Guessed the password with 67 queries.
2 Correct 6 ms 248 KB Guessed the password with 118 queries.
3 Correct 5 ms 248 KB Guessed the password with 48 queries.
4 Correct 5 ms 376 KB Guessed the password with 127 queries.
5 Correct 6 ms 248 KB Guessed the password with 91 queries.
6 Correct 6 ms 376 KB Guessed the password with 202 queries.
7 Correct 42 ms 252 KB Guessed the password with 3605 queries.
8 Correct 50 ms 248 KB Guessed the password with 5123 queries.
9 Correct 70 ms 248 KB Guessed the password with 7162 queries.
10 Correct 94 ms 376 KB Guessed the password with 9144 queries.
11 Correct 136 ms 504 KB Guessed the password with 13830 queries.
12 Correct 115 ms 376 KB Guessed the password with 11513 queries.
13 Correct 148 ms 504 KB Guessed the password with 14868 queries.
14 Correct 136 ms 464 KB Guessed the password with 13608 queries.
15 Correct 125 ms 328 KB Guessed the password with 15412 queries.
16 Correct 138 ms 472 KB Guessed the password with 14007 queries.
17 Correct 173 ms 376 KB Guessed the password with 16515 queries.
18 Correct 137 ms 248 KB Guessed the password with 14026 queries.
19 Correct 168 ms 508 KB Guessed the password with 17015 queries.
20 Correct 151 ms 376 KB Guessed the password with 13944 queries.
21 Correct 185 ms 432 KB Guessed the password with 17293 queries.
22 Correct 151 ms 248 KB Guessed the password with 15005 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Guessed the password with 67 queries.
2 Correct 6 ms 248 KB Guessed the password with 118 queries.
3 Correct 5 ms 248 KB Guessed the password with 48 queries.
4 Correct 5 ms 376 KB Guessed the password with 127 queries.
5 Correct 6 ms 248 KB Guessed the password with 91 queries.
6 Correct 6 ms 376 KB Guessed the password with 202 queries.
7 Correct 42 ms 252 KB Guessed the password with 3605 queries.
8 Correct 50 ms 248 KB Guessed the password with 5123 queries.
9 Correct 70 ms 248 KB Guessed the password with 7162 queries.
10 Correct 94 ms 376 KB Guessed the password with 9144 queries.
11 Correct 136 ms 504 KB Guessed the password with 13830 queries.
12 Correct 115 ms 376 KB Guessed the password with 11513 queries.
13 Correct 148 ms 504 KB Guessed the password with 14868 queries.
14 Correct 136 ms 464 KB Guessed the password with 13608 queries.
15 Correct 125 ms 328 KB Guessed the password with 15412 queries.
16 Correct 138 ms 472 KB Guessed the password with 14007 queries.
17 Correct 173 ms 376 KB Guessed the password with 16515 queries.
18 Correct 137 ms 248 KB Guessed the password with 14026 queries.
19 Correct 168 ms 508 KB Guessed the password with 17015 queries.
20 Correct 151 ms 376 KB Guessed the password with 13944 queries.
21 Correct 185 ms 432 KB Guessed the password with 17293 queries.
22 Correct 151 ms 248 KB Guessed the password with 15005 queries.
23 Correct 237 ms 424 KB Guessed the password with 24139 queries.
24 Correct 242 ms 420 KB Guessed the password with 23358 queries.
25 Correct 229 ms 488 KB Guessed the password with 24177 queries.
26 Correct 259 ms 700 KB Guessed the password with 24991 queries.
27 Correct 250 ms 600 KB Guessed the password with 24186 queries.
28 Correct 247 ms 528 KB Guessed the password with 24906 queries.
29 Correct 242 ms 528 KB Guessed the password with 24209 queries.
30 Correct 242 ms 536 KB Guessed the password with 24186 queries.