oj.uz

Submission #709186

# Submission time Handle Problem Language Result Execution time Memory
709186 2023-03-13T07:24:33 Z Halogen Password (RMI18_password) C++14
50 / 100
 385 ms 484 KB 
#include <bits/stdc++.h>

using namespace std;

int query(string q);

string guess(int n, int s) {
    string ans = "";

    set<char> remaining;
    int amt[s + 5];
    int cnt = 0;
    for (char i = 0; i < s; i++) {
        string g(n, i + 'a');
        amt[i] = query(g);
        cnt += amt[i];

        if (amt[i] > 0) remaining.insert(i);
        if (cnt == n) break;
        if (amt[i] == n) return g;
    }

    for (int k = 0; k < n; k++) {
        char cur = *remaining.begin();
        for (char i : remaining) {
            if (i == cur) continue;
            string g(amt[cur], 'a' + cur);
            g += ('a' + i);
            g += ans;
            int res = query(g);

            if (res != g.size()) continue;
            cur = i;
        }

        ans = string(1, 'a' + cur) + ans;
        amt[cur]--;

        if (amt[cur] == 0) remaining.erase(cur);
        if (remaining.size() == 1) {
            cur = *remaining.begin();
            string g(amt[cur], 'a' + cur);
            return g + ans;
        }
    }

    return ans;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:15:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   15 |         amt[i] = query(g);
      |             ^
password.cpp:16:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   16 |         cnt += amt[i];
      |                    ^
password.cpp:18:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   18 |         if (amt[i] > 0) remaining.insert(i);
      |                 ^
password.cpp:20:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |         if (amt[i] == n) return g;
      |                 ^
password.cpp:27:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   27 |             string g(amt[cur], 'a' + cur);
      |                          ^~~
password.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             if (res != g.size()) continue;
      |                 ~~~~^~~~~~~~~~~
password.cpp:37:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |         amt[cur]--;
      |             ^~~
password.cpp:39:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |         if (amt[cur] == 0) remaining.erase(cur);
      |                 ^~~
password.cpp:42:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |             string g(amt[cur], 'a' + cur);
      |                          ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 121 queries.
2 Correct 3 ms 208 KB Guessed the password with 277 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 48 queries.
2 Correct 2 ms 208 KB Guessed the password with 136 queries.
3 Correct 1 ms 208 KB Guessed the password with 18 queries.
4 Correct 3 ms 208 KB Guessed the password with 295 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 356 KB Guessed the password with 9307 queries.
2 Correct 89 ms 372 KB Guessed the password with 17735 queries.
3 Correct 126 ms 484 KB Guessed the password with 20689 queries.
4 Correct 385 ms 424 KB Guessed the password with 37112 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 121 queries.
2 Correct 3 ms 208 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 136 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 3 ms 208 KB Guessed the password with 295 queries.
7 Correct 99 ms 356 KB Guessed the password with 9307 queries.
8 Correct 89 ms 372 KB Guessed the password with 17735 queries.
9 Correct 126 ms 484 KB Guessed the password with 20689 queries.
10 Correct 385 ms 424 KB Guessed the password with 37112 queries.
11 Correct 364 ms 360 KB Guessed the password with 41054 queries.
12 Incorrect 353 ms 308 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 121 queries.
2 Correct 3 ms 208 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 48 queries.
4 Correct 2 ms 208 KB Guessed the password with 136 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 3 ms 208 KB Guessed the password with 295 queries.
7 Correct 99 ms 356 KB Guessed the password with 9307 queries.
8 Correct 89 ms 372 KB Guessed the password with 17735 queries.
9 Correct 126 ms 484 KB Guessed the password with 20689 queries.
10 Correct 385 ms 424 KB Guessed the password with 37112 queries.
11 Correct 364 ms 360 KB Guessed the password with 41054 queries.
12 Incorrect 353 ms 308 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -