oj.uz

Submission #246269

# Submission time Handle Problem Language Result Execution time Memory
246269 2020-07-08T13:25:14 Z kevlee Password (RMI18_password) C++17
50 / 100
 651 ms 632 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a));
#define all(x) (x).begin(), (x).end()
#define flush fflush(stdout)
#define debug printf("Hello\n")
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
//priority_queue <int, vector <int>, greater <int> > pq;
int query(string str);
int freq[30];
string guess(int n, int s) {
  string ret;
  FOR(i, 0, s-1) {
    char c = 'a' + i;
    string q(n, c);
    freq[i] = query(q);
  }
  int st = 0;
  FOR(i, 0, s-1) {
    if (freq[i] > 0) {
      char c = i + 'a';
      FOR(j, 1, freq[i]) {
        ret += c;
      }
      st = i + 1;
      break;
    }
  }
  int curlen = ret.length();
  FOR(i, st, s-1) {
    char c = i + 'a';
    string ch;
    ch += c;
    int pos = -1; //insert new letter just after position pos
    string q;
    while (true) {
      if (freq[i] == 0) break;
      if (pos == -1) {
        q = ch + ret;
      } else {
        q = ret.substr(0, pos+1) + ch;
        q += ret.substr(pos+1, curlen - pos - 1);
      }
      if (query(q) == curlen + 1) {
        ret = q;
        curlen++;
        pos++;
        freq[i]--;
      } else {
        pos++;
      }
      if (pos >= curlen) break;
    }
  }
  return ret;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Guessed the password with 48 queries.
2 Correct 5 ms 256 KB Guessed the password with 116 queries.
3 Correct 6 ms 384 KB Guessed the password with 93 queries.
4 Correct 9 ms 256 KB Guessed the password with 221 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 480 KB Guessed the password with 4580 queries.
2 Correct 120 ms 256 KB Guessed the password with 10213 queries.
3 Correct 134 ms 380 KB Guessed the password with 12520 queries.
4 Correct 279 ms 504 KB Guessed the password with 20417 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 76 queries.
2 Correct 7 ms 256 KB Guessed the password with 187 queries.
3 Correct 5 ms 256 KB Guessed the password with 48 queries.
4 Correct 5 ms 256 KB Guessed the password with 116 queries.
5 Correct 6 ms 384 KB Guessed the password with 93 queries.
6 Correct 9 ms 256 KB Guessed the password with 221 queries.
7 Correct 54 ms 480 KB Guessed the password with 4580 queries.
8 Correct 120 ms 256 KB Guessed the password with 10213 queries.
9 Correct 134 ms 380 KB Guessed the password with 12520 queries.
10 Correct 279 ms 504 KB Guessed the password with 20417 queries.
11 Correct 651 ms 504 KB Guessed the password with 49512 queries.
12 Correct 138 ms 392 KB Guessed the password with 11399 queries.
13 Correct 591 ms 380 KB Guessed the password with 47683 queries.
14 Correct 286 ms 520 KB Guessed the password with 21361 queries.
15 Correct 506 ms 632 KB Guessed the password with 44836 queries.
16 Correct 270 ms 376 KB Guessed the password with 17948 queries.
17 Execution timed out 602 ms 508 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Guessed the password with 76 queries.
2 Correct 7 ms 256 KB Guessed the password with 187 queries.
3 Correct 5 ms 256 KB Guessed the password with 48 queries.
4 Correct 5 ms 256 KB Guessed the password with 116 queries.
5 Correct 6 ms 384 KB Guessed the password with 93 queries.
6 Correct 9 ms 256 KB Guessed the password with 221 queries.
7 Correct 54 ms 480 KB Guessed the password with 4580 queries.
8 Correct 120 ms 256 KB Guessed the password with 10213 queries.
9 Correct 134 ms 380 KB Guessed the password with 12520 queries.
10 Correct 279 ms 504 KB Guessed the password with 20417 queries.
11 Correct 651 ms 504 KB Guessed the password with 49512 queries.
12 Correct 138 ms 392 KB Guessed the password with 11399 queries.
13 Correct 591 ms 380 KB Guessed the password with 47683 queries.
14 Correct 286 ms 520 KB Guessed the password with 21361 queries.
15 Correct 506 ms 632 KB Guessed the password with 44836 queries.
16 Correct 270 ms 376 KB Guessed the password with 17948 queries.
17 Execution timed out 602 ms 508 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -