oj.uz

Submission #872983

# Submission time Handle Problem Language Result Execution time Memory
872983 2023-11-14T08:29:16 Z vjudge1 Password (RMI18_password) C++17
10 / 100
 219 ms 24740 KB 
#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;
					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

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:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |      if(query(t) != t.size()) l = mid + 1;
      |         ~~~~~~~~~^~~~~~~~~~~
password.cpp:43:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |     if(last) g[c][i].push_back({d, last});
      |                ^
password.cpp:48:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   48 |   if(cnt[c] && !us[c][1]) dfs(c, 1);
      |          ^
password.cpp:48:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   48 |   if(cnt[c] && !us[c][1]) dfs(c, 1);
      |                    ^

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 23976 KB Returned early from guess() after 224 queries.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 24740 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 6 ms 23972 KB Guessed the password with 226 queries.
2 Correct 7 ms 24224 KB Guessed the password with 530 queries.
3 Incorrect 6 ms 23976 KB Returned early from guess() after 224 queries.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23972 KB Guessed the password with 226 queries.
2 Correct 7 ms 24224 KB Guessed the password with 530 queries.
3 Incorrect 6 ms 23976 KB Returned early from guess() after 224 queries.
4 Halted 0 ms 0 KB -