oj.uz

Submission #1064768

# Submission time Handle Problem Language Result Execution time Memory
1064768 2024-08-18T17:35:05 Z AlgorithmWarrior Password (RMI18_password) C++14
100 / 100
 232 ms 1508 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 <queue>
#include <cstring>

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 str);

class cmp
{
public:
    bool operator()(string a,string b)
    {
        return a.size()>b.size();
    }
};

string guess(int n, int s)
{
    int cnt[300]={0};
    char ch;
    priority_queue<string,vector<string>,cmp>pq;
    for(ch='a';ch<'a'+s;++ch)
    {
        int i;
        string s="";
        for(i=1,s=ch;s.size()<=n && query(s)==s.size();++i,s+=ch);
        cnt[ch]=i-1;
        s.pop_back();
        if(s.size())
            pq.push(s);
    }
    while(pq.size()>1)
    {
        string s1=pq.top(); pq.pop();
        string s2=pq.top(); pq.pop();
        int i,j=0;
        int siz=s1.size();
        int siz2=s2.size();
        string rez="";
        for(i=0;i<=siz;++i)
        {
            while(j<siz2 && query(rez+s2[j]+s1.substr(i,siz-i))==(rez+s2[j]+s1.substr(i,siz-i)).size())
                rez+=s2[j++];
            if(i<siz)
                rez+=s1[i];
        }
        pq.push(rez);
    }
    return pq.top();
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:56:30: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |         for(i=1,s=ch;s.size()<=n && query(s)==s.size();++i,s+=ch);
      |                      ~~~~~~~~^~~
password.cpp:56:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(i=1,s=ch;s.size()<=n && query(s)==s.size();++i,s+=ch);
      |                                     ~~~~~~~~^~~~~~~~~~
password.cpp:57:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   57 |         cnt[ch]=i-1;
      |             ^~
password.cpp:72:64: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             while(j<siz2 && query(rez+s2[j]+s1.substr(i,siz-i))==(rez+s2[j]+s1.substr(i,siz-i)).size())
      |                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
password.cpp:49:9: warning: variable 'cnt' set but not used [-Wunused-but-set-variable]
   49 |     int cnt[300]={0};
      |         ^~~
password.cpp: At global scope:
password.cpp:31:13: warning: 'void end(int)' defined but not used [-Wunused-function]
   31 | static void end(int success) {
      |             ^~~
password.cpp:28:18: warning: 'numQueries' defined but not used [-Wunused-variable]
   28 | static int n, s, numQueries;
      |                  ^~~~~~~~~~
password.cpp:28:15: warning: 's' defined but not used [-Wunused-variable]
   28 | static int n, s, numQueries;
      |               ^
password.cpp:28:12: warning: 'n' defined but not used [-Wunused-variable]
   28 | static int n, s, numQueries;
      |            ^

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 98 queries.
2 Correct 1 ms 600 KB Guessed the password with 163 queries.
3 Correct 1 ms 344 KB Guessed the password with 181 queries.
4 Correct 1 ms 344 KB Guessed the password with 280 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 848 KB Guessed the password with 3762 queries.
2 Correct 31 ms 444 KB Guessed the password with 6406 queries.
3 Correct 38 ms 592 KB Guessed the password with 6201 queries.
4 Correct 66 ms 496 KB Guessed the password with 10101 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 78 queries.
2 Correct 1 ms 344 KB Guessed the password with 143 queries.
3 Correct 1 ms 344 KB Guessed the password with 98 queries.
4 Correct 1 ms 600 KB Guessed the password with 163 queries.
5 Correct 1 ms 344 KB Guessed the password with 181 queries.
6 Correct 1 ms 344 KB Guessed the password with 280 queries.
7 Correct 24 ms 848 KB Guessed the password with 3762 queries.
8 Correct 31 ms 444 KB Guessed the password with 6406 queries.
9 Correct 38 ms 592 KB Guessed the password with 6201 queries.
10 Correct 66 ms 496 KB Guessed the password with 10101 queries.
11 Correct 73 ms 760 KB Guessed the password with 10984 queries.
12 Correct 73 ms 592 KB Guessed the password with 10984 queries.
13 Correct 90 ms 764 KB Guessed the password with 14548 queries.
14 Correct 91 ms 508 KB Guessed the password with 14683 queries.
15 Correct 100 ms 740 KB Guessed the password with 14111 queries.
16 Correct 102 ms 768 KB Guessed the password with 14074 queries.
17 Correct 96 ms 520 KB Guessed the password with 13540 queries.
18 Correct 107 ms 520 KB Guessed the password with 13577 queries.
19 Correct 94 ms 1016 KB Guessed the password with 13109 queries.
20 Correct 103 ms 964 KB Guessed the password with 13196 queries.
21 Correct 105 ms 724 KB Guessed the password with 15241 queries.
22 Correct 103 ms 528 KB Guessed the password with 15281 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 78 queries.
2 Correct 1 ms 344 KB Guessed the password with 143 queries.
3 Correct 1 ms 344 KB Guessed the password with 98 queries.
4 Correct 1 ms 600 KB Guessed the password with 163 queries.
5 Correct 1 ms 344 KB Guessed the password with 181 queries.
6 Correct 1 ms 344 KB Guessed the password with 280 queries.
7 Correct 24 ms 848 KB Guessed the password with 3762 queries.
8 Correct 31 ms 444 KB Guessed the password with 6406 queries.
9 Correct 38 ms 592 KB Guessed the password with 6201 queries.
10 Correct 66 ms 496 KB Guessed the password with 10101 queries.
11 Correct 73 ms 760 KB Guessed the password with 10984 queries.
12 Correct 73 ms 592 KB Guessed the password with 10984 queries.
13 Correct 90 ms 764 KB Guessed the password with 14548 queries.
14 Correct 91 ms 508 KB Guessed the password with 14683 queries.
15 Correct 100 ms 740 KB Guessed the password with 14111 queries.
16 Correct 102 ms 768 KB Guessed the password with 14074 queries.
17 Correct 96 ms 520 KB Guessed the password with 13540 queries.
18 Correct 107 ms 520 KB Guessed the password with 13577 queries.
19 Correct 94 ms 1016 KB Guessed the password with 13109 queries.
20 Correct 103 ms 964 KB Guessed the password with 13196 queries.
21 Correct 105 ms 724 KB Guessed the password with 15241 queries.
22 Correct 103 ms 528 KB Guessed the password with 15281 queries.
23 Correct 212 ms 876 KB Guessed the password with 28761 queries.
24 Correct 190 ms 1056 KB Guessed the password with 26005 queries.
25 Correct 232 ms 1508 KB Guessed the password with 28746 queries.
26 Correct 165 ms 808 KB Guessed the password with 24118 queries.
27 Correct 209 ms 1012 KB Guessed the password with 28735 queries.
28 Correct 167 ms 884 KB Guessed the password with 21855 queries.
29 Correct 202 ms 768 KB Guessed the password with 28731 queries.
30 Correct 151 ms 768 KB Guessed the password with 19415 queries.