oj.uz

Submission #872956

# Submission time Handle Problem Language Result Execution time Memory
872956 2023-11-14T07:27:11 Z vjudge1 Password (RMI18_password) C++17
30 / 100
 245 ms 24428 KB 
#include<bits/stdc++.h>
using namespace std;

string ANS;
int cnt[200];
bool us[200][5010];
vector<pair<char, int>>g[200][5010];

void dfs(char c, int i){
	us[c][i] = 1;
	for(auto to: g[c][i]){
		if(!us[to.first][to.second])
			dfs(to.first, to.second);
	} ANS+=c;
}

int query(string q);

string guess(int n, int s) {
	string ans;
	for(int i=0; i<n; i++) ans += 'a';
	for(char c='a'; c<'a'+s; c++){
		for(int i=0; i<n; i++) ans[i] = c;
		cnt[c] = query(ans);
	}
	for(char c='a'; c<'a'+s; c++){
		string ok;
		for(int i=1; i<=cnt[c]; i++){
			ok += c;
			if(i != cnt[c]) g[c][i].push_back({c, i+1});
			for(char d='a'; d<'a'+s; d++){
				if(c == d) continue;
				int last = 0;
				string t = ok;
				for(int j=1; j<=cnt[d]; j++){
					t += d;
					if(query(t) == t.size()){
						last = cnt[d]-j+1;
					}
				}
				if(last) g[c][i].push_back({d, last});
			}
		}
	}
	for(char c='a'; c<'a'+s; c++){
		if(cnt[c] && !us[c][1]) dfs(c, 1);
	} reverse(ANS.begin(), ANS.end());
	return ANS;
}

Compilation message

password.cpp: In function 'void dfs(char, int)':
password.cpp:10:5: warning: array subscript has type 'char' [-Wchar-subscripts]
   10 |  us[c][i] = 1;
      |     ^
password.cpp:11:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   11 |  for(auto to: g[c][i]){
      |                 ^
password.cpp:12:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   12 |   if(!us[to.first][to.second])
      |          ~~~^~~~~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:24:7: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |   cnt[c] = query(ans);
      |       ^
password.cpp:28:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   28 |   for(int i=1; i<=cnt[c]; i++){
      |                       ^
password.cpp:30:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   30 |    if(i != cnt[c]) g[c][i].push_back({c, i+1});
      |                ^
password.cpp:30:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   30 |    if(i != cnt[c]) g[c][i].push_back({c, i+1});
      |                      ^
password.cpp:35:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   35 |     for(int j=1; j<=cnt[d]; j++){
      |                         ^
password.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |      if(query(t) == t.size()){
      |         ~~~~~~~~~^~~~~~~~~~~
password.cpp:38:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   38 |       last = cnt[d]-j+1;
      |                  ^
password.cpp:41:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   41 |     if(last) g[c][i].push_back({d, last});
      |                ^
password.cpp:46:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   46 |   if(cnt[c] && !us[c][1]) dfs(c, 1);
      |          ^
password.cpp:46:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   46 |   if(cnt[c] && !us[c][1]) dfs(c, 1);
      |                    ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23972 KB Guessed the password with 226 queries.
2 Correct 8 ms 24224 KB Guessed the password with 530 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23976 KB Guessed the password with 1251 queries.
2 Correct 17 ms 24428 KB Guessed the password with 2308 queries.
3 Correct 16 ms 23968 KB Guessed the password with 1916 queries.
4 Correct 38 ms 23968 KB Guessed the password with 6631 queries.

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 245 ms 23976 KB Could not guess the password with 50000 queries.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23972 KB Guessed the password with 226 queries.
2 Correct 8 ms 24224 KB Guessed the password with 530 queries.
3 Correct 12 ms 23976 KB Guessed the password with 1251 queries.
4 Correct 17 ms 24428 KB Guessed the password with 2308 queries.
5 Correct 16 ms 23968 KB Guessed the password with 1916 queries.
6 Correct 38 ms 23968 KB Guessed the password with 6631 queries.
7 Incorrect 245 ms 23976 KB Could not guess the password with 50000 queries.
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23972 KB Guessed the password with 226 queries.
2 Correct 8 ms 24224 KB Guessed the password with 530 queries.
3 Correct 12 ms 23976 KB Guessed the password with 1251 queries.
4 Correct 17 ms 24428 KB Guessed the password with 2308 queries.
5 Correct 16 ms 23968 KB Guessed the password with 1916 queries.
6 Correct 38 ms 23968 KB Guessed the password with 6631 queries.
7 Incorrect 245 ms 23976 KB Could not guess the password with 50000 queries.
8 Halted 0 ms 0 KB -