oj.uz

Submission #858023

# Submission time Handle Problem Language Result Execution time Memory
858023 2023-10-07T10:29:37 Z Pety Password (RMI18_password) C++14
80 / 100
 255 ms 1380 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>
#include <algorithm>

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];

pair<int, char>pp[30];

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 < s; i++)
    pp[i] = {fr[i], 'a' + i};
  sort(pp, pp + s);
  for (int i = 0; i < pp[0].first; i++)
    a += pp[0].second;
  for (int i = 1; i < s; i++) {
    string b;
    for (int j = 0; j < pp[i].first; j++)
      b += pp[i].second;
    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 += pp[i].second;
      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

password.cpp: In function 'std::string guess(int, int)':
password.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int j = 0; j <= a.size(); j++) {
      |                     ~~^~~~~~~~~~~
password.cpp:118:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |       if (j < a.size())
      |           ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 135 queries.
2 Correct 2 ms 344 KB Guessed the password with 299 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Guessed the password with 28 queries.
2 Correct 0 ms 344 KB Guessed the password with 34 queries.
3 Correct 1 ms 344 KB Guessed the password with 20 queries.
4 Correct 1 ms 344 KB Guessed the password with 93 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1200 KB Guessed the password with 2160 queries.
2 Correct 37 ms 1204 KB Guessed the password with 8449 queries.
3 Correct 25 ms 948 KB Guessed the password with 3638 queries.
4 Correct 49 ms 736 KB Guessed the password with 12061 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 135 queries.
2 Correct 2 ms 344 KB Guessed the password with 299 queries.
3 Correct 0 ms 596 KB Guessed the password with 28 queries.
4 Correct 0 ms 344 KB Guessed the password with 34 queries.
5 Correct 1 ms 344 KB Guessed the password with 20 queries.
6 Correct 1 ms 344 KB Guessed the password with 93 queries.
7 Correct 8 ms 1200 KB Guessed the password with 2160 queries.
8 Correct 37 ms 1204 KB Guessed the password with 8449 queries.
9 Correct 25 ms 948 KB Guessed the password with 3638 queries.
10 Correct 49 ms 736 KB Guessed the password with 12061 queries.
11 Correct 28 ms 700 KB Guessed the password with 6648 queries.
12 Correct 33 ms 964 KB Guessed the password with 6681 queries.
13 Correct 67 ms 972 KB Guessed the password with 15007 queries.
14 Correct 71 ms 708 KB Guessed the password with 15385 queries.
15 Correct 51 ms 712 KB Guessed the password with 11319 queries.
16 Correct 46 ms 976 KB Guessed the password with 11223 queries.
17 Correct 41 ms 724 KB Guessed the password with 8978 queries.
18 Correct 41 ms 712 KB Guessed the password with 9060 queries.
19 Correct 34 ms 724 KB Guessed the password with 7637 queries.
20 Correct 38 ms 740 KB Guessed the password with 7860 queries.
21 Correct 61 ms 984 KB Guessed the password with 11829 queries.
22 Correct 51 ms 1216 KB Guessed the password with 11947 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 135 queries.
2 Correct 2 ms 344 KB Guessed the password with 299 queries.
3 Correct 0 ms 596 KB Guessed the password with 28 queries.
4 Correct 0 ms 344 KB Guessed the password with 34 queries.
5 Correct 1 ms 344 KB Guessed the password with 20 queries.
6 Correct 1 ms 344 KB Guessed the password with 93 queries.
7 Correct 8 ms 1200 KB Guessed the password with 2160 queries.
8 Correct 37 ms 1204 KB Guessed the password with 8449 queries.
9 Correct 25 ms 948 KB Guessed the password with 3638 queries.
10 Correct 49 ms 736 KB Guessed the password with 12061 queries.
11 Correct 28 ms 700 KB Guessed the password with 6648 queries.
12 Correct 33 ms 964 KB Guessed the password with 6681 queries.
13 Correct 67 ms 972 KB Guessed the password with 15007 queries.
14 Correct 71 ms 708 KB Guessed the password with 15385 queries.
15 Correct 51 ms 712 KB Guessed the password with 11319 queries.
16 Correct 46 ms 976 KB Guessed the password with 11223 queries.
17 Correct 41 ms 724 KB Guessed the password with 8978 queries.
18 Correct 41 ms 712 KB Guessed the password with 9060 queries.
19 Correct 34 ms 724 KB Guessed the password with 7637 queries.
20 Correct 38 ms 740 KB Guessed the password with 7860 queries.
21 Correct 61 ms 984 KB Guessed the password with 11829 queries.
22 Correct 51 ms 1216 KB Guessed the password with 11947 queries.
23 Incorrect 255 ms 1380 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -