Submission #872980

#	Time	Username	Problem	Language	Result	Execution time	Memory
872980		vjudge1	Password (RMI18_password)	C++17	10 / 100	242 ms	24816 KiB

password

#include<bits/stdc++.h>
using namespace std;

string ANS;
int cnt[200];
int ZAPARIL;
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 l=1, r=cnt[d]; l<=r;){
					int mid = l+r>>1;
					while(t.size()-i > mid) t.pop_back();
					while(t.size()-i < mid) t += d;
					ZAPARIL++;
					if(ZAPARIL > 50000){
						cout << "CHORT\nDURSTAP JAZBAISNBA\n";
						for(int i=1; i<1e9; i++){
							cout << "TL ";
						}
					}
					if(query(t) != t.size()) l = mid + 1;
					else r = mid - 1, last = mid;
				}
				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:11:5: warning: array subscript has type 'char' [-Wchar-subscripts]
   11 |  us[c][i] = 1;
      |     ^
password.cpp:12:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   12 |  for(auto to: g[c][i]){
      |                 ^
password.cpp:13:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   13 |   if(!us[to.first][to.second])
      |          ~~~^~~~~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:25:7: warning: array subscript has type 'char' [-Wchar-subscripts]
   25 |   cnt[c] = query(ans);
      |       ^
password.cpp:29:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   29 |   for(int i=1; i<=cnt[c]; i++){
      |                       ^
password.cpp:31:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |    if(i != cnt[c]) g[c][i].push_back({c, i+1});
      |                ^
password.cpp:31:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |    if(i != cnt[c]) g[c][i].push_back({c, i+1});
      |                      ^
password.cpp:36:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   36 |     for(int l=1, r=cnt[d]; l<=r;){
      |                        ^
password.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |      int mid = l+r>>1;
      |                ~^~
password.cpp:38:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |      while(t.size()-i > mid) t.pop_back();
      |            ~~~~~~~~~~~^~~~~
password.cpp:39:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |      while(t.size()-i < mid) t += d;
      |            ~~~~~~~~~~~^~~~~
password.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |      if(query(t) != t.size()) l = mid + 1;
      |         ~~~~~~~~~^~~~~~~~~~~
password.cpp:50:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |     if(last) g[c][i].push_back({d, last});
      |                ^
password.cpp:55:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   55 |   if(cnt[c] && !us[c][1]) dfs(c, 1);
      |          ^
password.cpp:55:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   55 |   if(cnt[c] && !us[c][1]) dfs(c, 1);
      |                    ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20