oj.uz

Submission #773301

# Submission time Handle Problem Language Result Execution time Memory
773301 2023-07-04T20:19:09 Z BT21tata Password (RMI18_password) C++17
100 / 100
 265 ms 496 KB 
#include <bits/stdc++.h>
using namespace std;

struct cmp
{
 	bool operator()(const string &a, const string &b)
  	{
    	return a.size()>b.size();
  	}
};

int query(string str);

string mrg(string &a, string &b)
{
  	string ret, cur;
  	int pos1=0, pos2=0;
  	while(true)
  	{
    	if(pos1==a.size() or pos2==b.size()) break;
    	cur=ret;
    	cur+=a[pos1];
    	for(int i=pos2; i<b.size(); i++)
      		cur+=b[i];
    	int q=query(cur);
    	if(q==pos1+b.size()+1)
      		ret+=a[pos1++];
    	else ret+=b[pos2++];
  	}
  	while(pos1<a.size()) ret+=a[pos1++];
  	while(pos2<b.size()) ret+=b[pos2++];
  	return ret;
}


string guess(int n, int s)
{
  	priority_queue<string, vector<string>, cmp>q;
  	for(int i=0; i<s; i++)
  	{
    	string ss, sec;
    	for(int j=0; j<n; j++)
      		ss+=(char)(i+'a');
    	int ret=query(ss);

    	if(!ret) continue;
    	for(int j=0; j<ret; j++)
     		sec+=(char)(i+'a');

    	q.push(sec);
  	}

  	while(q.size()>1)
  	{
    	string s1=q.top(); q.pop();
    	string s2=q.top(); q.pop();
    	string merged=mrg(s1, s2);
    	q.push(merged);
  	}
  	return q.top();
}

Compilation message

password.cpp: In function 'std::string mrg(std::string&, std::string&)':
password.cpp:20:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |      if(pos1==a.size() or pos2==b.size()) break;
      |         ~~~~^~~~~~~~~~
password.cpp:20:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |      if(pos1==a.size() or pos2==b.size()) break;
      |                           ~~~~^~~~~~~~~~
password.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |      for(int i=pos2; i<b.size(); i++)
      |                      ~^~~~~~~~~
password.cpp:26:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |      if(q==pos1+b.size()+1)
      |         ~^~~~~~~~~~~~~~~~~
password.cpp:30:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    while(pos1<a.size()) ret+=a[pos1++];
      |          ~~~~^~~~~~~~~
password.cpp:31:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    while(pos2<b.size()) ret+=b[pos2++];
      |          ~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 57 queries.
2 Correct 1 ms 208 KB Guessed the password with 105 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 49 queries.
2 Correct 1 ms 208 KB Guessed the password with 90 queries.
3 Correct 1 ms 208 KB Guessed the password with 92 queries.
4 Correct 2 ms 208 KB Guessed the password with 178 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 208 KB Guessed the password with 2750 queries.
2 Correct 23 ms 308 KB Guessed the password with 5071 queries.
3 Correct 37 ms 296 KB Guessed the password with 4587 queries.
4 Correct 65 ms 332 KB Guessed the password with 8084 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 57 queries.
2 Correct 1 ms 208 KB Guessed the password with 105 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 1 ms 208 KB Guessed the password with 92 queries.
6 Correct 2 ms 208 KB Guessed the password with 178 queries.
7 Correct 24 ms 208 KB Guessed the password with 2750 queries.
8 Correct 23 ms 308 KB Guessed the password with 5071 queries.
9 Correct 37 ms 296 KB Guessed the password with 4587 queries.
10 Correct 65 ms 332 KB Guessed the password with 8084 queries.
11 Correct 82 ms 336 KB Guessed the password with 8161 queries.
12 Correct 64 ms 432 KB Guessed the password with 8160 queries.
13 Correct 93 ms 336 KB Guessed the password with 11502 queries.
14 Correct 83 ms 312 KB Guessed the password with 11602 queries.
15 Correct 59 ms 296 KB Guessed the password with 10881 queries.
16 Correct 104 ms 340 KB Guessed the password with 10861 queries.
17 Correct 83 ms 332 KB Guessed the password with 10211 queries.
18 Correct 87 ms 336 KB Guessed the password with 10249 queries.
19 Correct 90 ms 424 KB Guessed the password with 9685 queries.
20 Correct 67 ms 348 KB Guessed the password with 9777 queries.
21 Correct 113 ms 440 KB Guessed the password with 11644 queries.
22 Correct 105 ms 340 KB Guessed the password with 11713 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 57 queries.
2 Correct 1 ms 208 KB Guessed the password with 105 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.
5 Correct 1 ms 208 KB Guessed the password with 92 queries.
6 Correct 2 ms 208 KB Guessed the password with 178 queries.
7 Correct 24 ms 208 KB Guessed the password with 2750 queries.
8 Correct 23 ms 308 KB Guessed the password with 5071 queries.
9 Correct 37 ms 296 KB Guessed the password with 4587 queries.
10 Correct 65 ms 332 KB Guessed the password with 8084 queries.
11 Correct 82 ms 336 KB Guessed the password with 8161 queries.
12 Correct 64 ms 432 KB Guessed the password with 8160 queries.
13 Correct 93 ms 336 KB Guessed the password with 11502 queries.
14 Correct 83 ms 312 KB Guessed the password with 11602 queries.
15 Correct 59 ms 296 KB Guessed the password with 10881 queries.
16 Correct 104 ms 340 KB Guessed the password with 10861 queries.
17 Correct 83 ms 332 KB Guessed the password with 10211 queries.
18 Correct 87 ms 336 KB Guessed the password with 10249 queries.
19 Correct 90 ms 424 KB Guessed the password with 9685 queries.
20 Correct 67 ms 348 KB Guessed the password with 9777 queries.
21 Correct 113 ms 440 KB Guessed the password with 11644 queries.
22 Correct 105 ms 340 KB Guessed the password with 11713 queries.
23 Correct 202 ms 412 KB Guessed the password with 23648 queries.
24 Correct 152 ms 356 KB Guessed the password with 20965 queries.
25 Correct 183 ms 496 KB Guessed the password with 23669 queries.
26 Correct 183 ms 480 KB Guessed the password with 19098 queries.
27 Correct 265 ms 476 KB Guessed the password with 23721 queries.
28 Correct 168 ms 464 KB Guessed the password with 16823 queries.
29 Correct 189 ms 360 KB Guessed the password with 23707 queries.
30 Correct 141 ms 348 KB Guessed the password with 14393 queries.