oj.uz

Submission #246266

# Submission time Handle Problem Language Result Execution time Memory
246266 2020-07-08T13:16:17 Z kevlee Password (RMI18_password) C++17
50 / 100
 608 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 6 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 6 ms 256 KB Guessed the password with 116 queries.
3 Correct 5 ms 256 KB Guessed the password with 93 queries.
4 Correct 7 ms 256 KB Guessed the password with 221 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 504 KB Guessed the password with 4580 queries.
2 Correct 141 ms 384 KB Guessed the password with 10213 queries.
3 Correct 154 ms 376 KB Guessed the password with 12520 queries.
4 Correct 258 ms 496 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 6 ms 256 KB Guessed the password with 187 queries.
3 Correct 5 ms 256 KB Guessed the password with 48 queries.
4 Correct 6 ms 256 KB Guessed the password with 116 queries.
5 Correct 5 ms 256 KB Guessed the password with 93 queries.
6 Correct 7 ms 256 KB Guessed the password with 221 queries.
7 Correct 59 ms 504 KB Guessed the password with 4580 queries.
8 Correct 141 ms 384 KB Guessed the password with 10213 queries.
9 Correct 154 ms 376 KB Guessed the password with 12520 queries.
10 Correct 258 ms 496 KB Guessed the password with 20417 queries.
11 Correct 603 ms 384 KB Guessed the password with 49512 queries.
12 Correct 144 ms 632 KB Guessed the password with 11399 queries.
13 Correct 608 ms 384 KB Guessed the password with 47683 queries.
14 Correct 266 ms 504 KB Guessed the password with 21361 queries.
15 Correct 512 ms 392 KB Guessed the password with 44836 queries.
16 Correct 233 ms 504 KB Guessed the password with 17948 queries.
17 Execution timed out 581 ms 504 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 6 ms 256 KB Guessed the password with 187 queries.
3 Correct 5 ms 256 KB Guessed the password with 48 queries.
4 Correct 6 ms 256 KB Guessed the password with 116 queries.
5 Correct 5 ms 256 KB Guessed the password with 93 queries.
6 Correct 7 ms 256 KB Guessed the password with 221 queries.
7 Correct 59 ms 504 KB Guessed the password with 4580 queries.
8 Correct 141 ms 384 KB Guessed the password with 10213 queries.
9 Correct 154 ms 376 KB Guessed the password with 12520 queries.
10 Correct 258 ms 496 KB Guessed the password with 20417 queries.
11 Correct 603 ms 384 KB Guessed the password with 49512 queries.
12 Correct 144 ms 632 KB Guessed the password with 11399 queries.
13 Correct 608 ms 384 KB Guessed the password with 47683 queries.
14 Correct 266 ms 504 KB Guessed the password with 21361 queries.
15 Correct 512 ms 392 KB Guessed the password with 44836 queries.
16 Correct 233 ms 504 KB Guessed the password with 17948 queries.
17 Execution timed out 581 ms 504 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -