| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 858020 | 2023-10-07T10:26:53 Z | Pety | Password (RMI18_password) | C++14 | 311 ms | 1196 KB |
// Sample grader for contestants' use.
//
// Usage: place your input data in the file password.in in the format
//
// line 1: N S
// line 2: hidden_password
//
// Then compile this grader together with your implementation.
// Run the binary to see your guessing strategy at work!
// Set DEBUG to 1 to print all queries.
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <vector>
using namespace std;
// #define DEBUG 0
// #define MAX_QUERIES 50000
// #define MAX_N 5000
// #define MAX_SIGMA 26
// static string password;
// static int n, s, numQueries;
// static stringstream msg;
// static void end(int success) {
// cout << (success ? "SUCCESS! " : "ERROR: ") << msg.str() << endl;
// exit(0);
// }
// int query(string q) {
// if (++numQueries > MAX_QUERIES) {
// msg << "Could not guess the password with " << MAX_QUERIES << " questions.";
// end(0);
// }
// int len = q.size();
// // validation
// if (len < 1 || len > n) {
// msg << "Query '" << q << "' should have length between 1 and "
// << n << " characters.";
// end(0);
// }
// for (int i = 0; i < len; i++) {
// if (q[i] < 'a' || q[i] >= 'a' + s) {
// msg << "Illegal character '" << q[i] << "' found.";
// end(0);
// }
// }
// // while possible, advance one character in q and find its next
// // occurrence in password
// int i = 0, j = 0, plen = password.size();
// while (i < plen && j < len) {
// while ((i < plen) && (password[i] != q[j])) {
// i++;
// }
// if (i < plen) {
// i++;
// j++;
// }
// }
// if (DEBUG) {
// cout << "Question #" << numQueries << " [" << q << "] answer " << j << endl;
// }
// return j;
// }
int query(string s);
int fr[26];
string guess (int n, int s) {
for (char c = 'a'; c < 'a' + s; c++) {
string s;
for (int i = 0; i < n; i++)
s += c;
fr[c - 'a'] = query(s);
}
string a;
for (int i = 0; i < fr[0]; i++)
a += 'a';
for (int i = 1; i < s; i++) {
string b;
for (int j = 0; j < fr[i]; j++)
b += 'a' + i;
string cp;
cp = a;
vector<int>p(a.size()+2);
int t = a.size();
int last = 0;
for (int j = 0; j <= t; j++) {
int x = query(a + b);
p[t - j] = x - a.size() - last;
last += p[t - j];
if (a.size())
a.pop_back();
}
a = cp;
b = "";
for (int j = 0; j <= a.size(); j++) {
for (int k = 0; k < p[j]; k++)
b += 'a' + i;
if (j < a.size())
b += a[j];
}
a = b;
}
return a;
}
// int main() {
// ifstream f("password.in");
// f >> n >> s >> password;
// f.close();
// assert(n && s && !password.empty());
// string answer = guess(n, s);
// if (DEBUG) {
// cout << "Your answer: [" << answer << "]\n";
// }
// if (answer.compare(password)) {
// msg << "Your answer was [" << answer
// << "] which does not match the password [" << password << "].";
// end(0);
// } else {
// msg << "You guessed the password with " << numQueries << " queries.";
// end(1);
// }
// return 0;
// }
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 344 KB | Guessed the password with 135 queries. |
| 2 | Correct | 1 ms | 344 KB | Guessed the password with 299 queries. |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 344 KB | Guessed the password with 28 queries. |
| 2 | Correct | 1 ms | 344 KB | Guessed the password with 108 queries. |
| 3 | Correct | 1 ms | 344 KB | Guessed the password with 28 queries. |
| 4 | Correct | 1 ms | 344 KB | Guessed the password with 136 queries. |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 16 ms | 1196 KB | Guessed the password with 3829 queries. |
| 2 | Correct | 44 ms | 712 KB | Guessed the password with 9488 queries. |
| 3 | Correct | 66 ms | 952 KB | Guessed the password with 12802 queries. |
| 4 | Correct | 102 ms | 940 KB | Guessed the password with 18914 queries. |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 344 KB | Guessed the password with 135 queries. |
| 2 | Correct | 1 ms | 344 KB | Guessed the password with 299 queries. |
| 3 | Correct | 0 ms | 344 KB | Guessed the password with 28 queries. |
| 4 | Correct | 1 ms | 344 KB | Guessed the password with 108 queries. |
| 5 | Correct | 1 ms | 344 KB | Guessed the password with 28 queries. |
| 6 | Correct | 1 ms | 344 KB | Guessed the password with 136 queries. |
| 7 | Correct | 16 ms | 1196 KB | Guessed the password with 3829 queries. |
| 8 | Correct | 44 ms | 712 KB | Guessed the password with 9488 queries. |
| 9 | Correct | 66 ms | 952 KB | Guessed the password with 12802 queries. |
| 10 | Correct | 102 ms | 940 KB | Guessed the password with 18914 queries. |
| 11 | Incorrect | 311 ms | 708 KB | Could not guess the password with 50000 queries. |
| 12 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 344 KB | Guessed the password with 135 queries. |
| 2 | Correct | 1 ms | 344 KB | Guessed the password with 299 queries. |
| 3 | Correct | 0 ms | 344 KB | Guessed the password with 28 queries. |
| 4 | Correct | 1 ms | 344 KB | Guessed the password with 108 queries. |
| 5 | Correct | 1 ms | 344 KB | Guessed the password with 28 queries. |
| 6 | Correct | 1 ms | 344 KB | Guessed the password with 136 queries. |
| 7 | Correct | 16 ms | 1196 KB | Guessed the password with 3829 queries. |
| 8 | Correct | 44 ms | 712 KB | Guessed the password with 9488 queries. |
| 9 | Correct | 66 ms | 952 KB | Guessed the password with 12802 queries. |
| 10 | Correct | 102 ms | 940 KB | Guessed the password with 18914 queries. |
| 11 | Incorrect | 311 ms | 708 KB | Could not guess the password with 50000 queries. |
| 12 | Halted | 0 ms | 0 KB | - |