oj.uz

Submission #872986

# Submission time Handle Problem Language Result Execution time Memory
872986 2023-11-14T08:35:42 Z vjudge1 Password (RMI18_password) C++17
30 / 100
 257 ms 24808 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);
		ZAPARIL++;
	}
	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){
						for(int i=1; i<=1e9; i++){
							cout << "tl";
						}
					}
					if(query(t) != t.size()) r = mid - 1;
					else l = mid + 1, last = cnt[d]-mid+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: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:30:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   30 |   for(int i=1; i<=cnt[c]; i++){
      |                       ^
password.cpp:32:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   32 |    if(i != cnt[c]) g[c][i].push_back({c, i+1});
      |                ^
password.cpp:32:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   32 |    if(i != cnt[c]) g[c][i].push_back({c, i+1});
      |                      ^
password.cpp:37:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |     for(int l=1, r=cnt[d]; l<=r;){
      |                        ^
password.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |      int mid = l+r>>1;
      |                ~^~
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.pop_back();
      |            ~~~~~~~~~~~^~~~~
password.cpp:40:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |      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()) r = mid - 1;
      |         ~~~~~~~~~^~~~~~~~~~~
password.cpp:48:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   48 |      else l = mid + 1, last = cnt[d]-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.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23972 KB Guessed the password with 242 queries.
2 Correct 8 ms 23968 KB Guessed the password with 537 queries.
3 Correct 9 ms 23972 KB Guessed the password with 570 queries.
4 Correct 11 ms 23976 KB Guessed the password with 1280 queries.

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 257 ms 24808 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23976 KB Guessed the password with 226 queries.
2 Correct 7 ms 23968 KB Guessed the password with 530 queries.
3 Correct 6 ms 23972 KB Guessed the password with 242 queries.
4 Correct 8 ms 23968 KB Guessed the password with 537 queries.
5 Correct 9 ms 23972 KB Guessed the password with 570 queries.
6 Correct 11 ms 23976 KB Guessed the password with 1280 queries.
7 Runtime error 257 ms 24808 KB Execution killed with signal 13
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23976 KB Guessed the password with 226 queries.
2 Correct 7 ms 23968 KB Guessed the password with 530 queries.
3 Correct 6 ms 23972 KB Guessed the password with 242 queries.
4 Correct 8 ms 23968 KB Guessed the password with 537 queries.
5 Correct 9 ms 23972 KB Guessed the password with 570 queries.
6 Correct 11 ms 23976 KB Guessed the password with 1280 queries.
7 Runtime error 257 ms 24808 KB Execution killed with signal 13
8 Halted 0 ms 0 KB -