Submission #872956

#	Time	Username	Problem	Language	Result	Execution time	Memory
872956		vjudge1	Password (RMI18_password)	C++17	30 / 100	245 ms	24428 KiB

password

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20