oj.uz

Submission #873083

# Submission time Handle Problem Language Result Execution time Memory
873083 2023-11-14T12:28:26 Z vjudge1 Password (RMI18_password) C++17
100 / 100
 176 ms 1928 KB 
#include<bits/stdc++.h>
using namespace std;

int cnt[26];
set<char>st[26];

int query(string q);

string guess(int n, int s) {
	set<pair<int, string>>st;
	for(char c='a'; c<'a'+s; c++){
		string d;
		for(int i=1; i<=n; i++)
			d += c;
		cnt[c-'a'] = query(d);
		while(d.size() > cnt[c-'a']) 
			d.pop_back();
		if(cnt[c-'a']) st.insert({d.size(), d});
	} 
	while(st.size() > 1){
		string a = st.begin()->second;
		st.erase(st.begin());
		string b = st.begin()->second;
		st.erase(st.begin());
		string c; int l = 0, r = 0;
		while(c.size() < a.size()+b.size()){
			if(r < b.size()){
				c += b[r];
			}
			for(int j=l; j<a.size(); j++) 
				c += a[j];
			if(r < b.size() && query(c) == c.size()){
				r++;
				for(int j=l; j<a.size(); j++)
					c.pop_back();
			} else{
				for(int j=l; j<a.size(); j++)
					c.pop_back();
				if(r < b.size()) c.pop_back();
				c += a[l++];
			}
		} st.insert({c.size(), c});
	}
	return st.begin()->second;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:16:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |   while(d.size() > cnt[c-'a'])
      |         ~~~~~~~~~^~~~~~~~~~~~
password.cpp:27:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    if(r < b.size()){
      |       ~~^~~~~~~~~~
password.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    for(int j=l; j<a.size(); j++)
      |                 ~^~~~~~~~~
password.cpp:32:9: 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(r < b.size() && query(c) == c.size()){
      |       ~~^~~~~~~~~~
password.cpp:32:32: 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(r < b.size() && query(c) == c.size()){
      |                       ~~~~~~~~~^~~~~~~~~~~
password.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int j=l; j<a.size(); j++)
      |                  ~^~~~~~~~~
password.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int j=l; j<a.size(); j++)
      |                  ~^~~~~~~~~
password.cpp:39:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     if(r < b.size()) c.pop_back();
      |        ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Guessed the password with 48 queries.
2 Correct 1 ms 344 KB Guessed the password with 93 queries.
3 Correct 1 ms 344 KB Guessed the password with 91 queries.
4 Correct 1 ms 344 KB Guessed the password with 180 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 956 KB Guessed the password with 2761 queries.
2 Correct 26 ms 1196 KB Guessed the password with 5104 queries.
3 Correct 26 ms 720 KB Guessed the password with 4605 queries.
4 Correct 50 ms 956 KB Guessed the password with 8101 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 62 queries.
2 Correct 1 ms 344 KB Guessed the password with 121 queries.
3 Correct 0 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 93 queries.
5 Correct 1 ms 344 KB Guessed the password with 91 queries.
6 Correct 1 ms 344 KB Guessed the password with 180 queries.
7 Correct 13 ms 956 KB Guessed the password with 2761 queries.
8 Correct 26 ms 1196 KB Guessed the password with 5104 queries.
9 Correct 26 ms 720 KB Guessed the password with 4605 queries.
10 Correct 50 ms 956 KB Guessed the password with 8101 queries.
11 Correct 52 ms 448 KB Guessed the password with 8178 queries.
12 Correct 54 ms 476 KB Guessed the password with 8184 queries.
13 Correct 70 ms 696 KB Guessed the password with 11549 queries.
14 Correct 72 ms 972 KB Guessed the password with 11679 queries.
15 Correct 70 ms 468 KB Guessed the password with 10910 queries.
16 Correct 69 ms 708 KB Guessed the password with 10880 queries.
17 Correct 69 ms 736 KB Guessed the password with 10245 queries.
18 Correct 68 ms 1216 KB Guessed the password with 10274 queries.
19 Correct 65 ms 708 KB Guessed the password with 9709 queries.
20 Correct 67 ms 708 KB Guessed the password with 9801 queries.
21 Correct 83 ms 712 KB Guessed the password with 11743 queries.
22 Correct 84 ms 1200 KB Guessed the password with 11781 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 62 queries.
2 Correct 1 ms 344 KB Guessed the password with 121 queries.
3 Correct 0 ms 344 KB Guessed the password with 48 queries.
4 Correct 1 ms 344 KB Guessed the password with 93 queries.
5 Correct 1 ms 344 KB Guessed the password with 91 queries.
6 Correct 1 ms 344 KB Guessed the password with 180 queries.
7 Correct 13 ms 956 KB Guessed the password with 2761 queries.
8 Correct 26 ms 1196 KB Guessed the password with 5104 queries.
9 Correct 26 ms 720 KB Guessed the password with 4605 queries.
10 Correct 50 ms 956 KB Guessed the password with 8101 queries.
11 Correct 52 ms 448 KB Guessed the password with 8178 queries.
12 Correct 54 ms 476 KB Guessed the password with 8184 queries.
13 Correct 70 ms 696 KB Guessed the password with 11549 queries.
14 Correct 72 ms 972 KB Guessed the password with 11679 queries.
15 Correct 70 ms 468 KB Guessed the password with 10910 queries.
16 Correct 69 ms 708 KB Guessed the password with 10880 queries.
17 Correct 69 ms 736 KB Guessed the password with 10245 queries.
18 Correct 68 ms 1216 KB Guessed the password with 10274 queries.
19 Correct 65 ms 708 KB Guessed the password with 9709 queries.
20 Correct 67 ms 708 KB Guessed the password with 9801 queries.
21 Correct 83 ms 712 KB Guessed the password with 11743 queries.
22 Correct 84 ms 1200 KB Guessed the password with 11781 queries.
23 Correct 176 ms 1592 KB Guessed the password with 23751 queries.
24 Correct 138 ms 1928 KB Guessed the password with 21005 queries.
25 Correct 170 ms 1636 KB Guessed the password with 23741 queries.
26 Correct 136 ms 1728 KB Guessed the password with 19118 queries.
27 Correct 171 ms 1236 KB Guessed the password with 23712 queries.
28 Correct 126 ms 976 KB Guessed the password with 16852 queries.
29 Correct 163 ms 1404 KB Guessed the password with 23732 queries.
30 Correct 116 ms 1472 KB Guessed the password with 14420 queries.