oj.uz

답안 #286981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
286981 2020-08-31T08:23:22 Z crossing0ver Password (RMI18_password) C++17
50 / 100
 530 ms 636 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;

int m;
string suf,pref;
int query(string str);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string guess(int n, int s) {
	string pref,P;
	vector<char> D;
	for (char i = 'a'; i < 'a' + s ; i++)
		D.pb(i);
	shuffle(all(D),rng);
	map<char,int> mp;
	for (int i = 0;i < s; i++) mp[D[i]] = i;
	char fs = 'a';
	for (; pref.size() + suf.size() <= n; ) {
		int len = suf.size() + pref.size();
		char LAST = ((int)pref.size() ? pref.back() : 'a');
		int cur = len;
//		vector<char> D = T;
		for (int z = 1; z + pref.size() + suf.size() <= n;) {
			bool flag = 0;
			vector<char> Q;
		//	shuffle(D.begin(),D.end(),rng);
		for (int  b= max((pref.size() ? mp[pref.back()] : 0),(suf.size() ? mp[suf[0]] : 0)); b < s; b++){
			char c = D[b];
	///	for (char c : D) {
			P = pref + c;
			P += suf;
			int F = query(P);
			if (F > cur) {
				LAST = c;
				pref += c;
				cur = F;
				flag  = 1;
				break;
			}
		//	else Q.pb(c);
		}
	//	for (char c :  Q) D.erase(find(all(D),c));
		if (flag == 0) break;
		}
		reverse(all(suf));
		if (pref.size())
		suf+=pref.back();
		reverse(all(suf));
		if (pref.size())
		pref.pop_back();
		if (pref.size() + suf.size() == n) {
			pref += suf;
			int Z = query(pref);
			return pref;
		}
	}
	pref += suf;
	int z = query(pref);
	return pref;
}
/*
main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

}*/

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:24:34: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |  for (; pref.size() + suf.size() <= n; ) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:29:48: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |   for (int z = 1; z + pref.size() + suf.size() <= n;) {
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:57:32: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |   if (pref.size() + suf.size() == n) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
password.cpp:59:8: warning: unused variable 'Z' [-Wunused-variable]
   59 |    int Z = query(pref);
      |        ^
password.cpp:26:8: warning: variable 'LAST' set but not used [-Wunused-but-set-variable]
   26 |   char LAST = ((int)pref.size() ? pref.back() : 'a');
      |        ^~~~
password.cpp:23:7: warning: unused variable 'fs' [-Wunused-variable]
   23 |  char fs = 'a';
      |       ^~
password.cpp:64:6: warning: unused variable 'z' [-Wunused-variable]
   64 |  int z = query(pref);
      |      ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Guessed the password with 130 queries.
2 Correct 4 ms 256 KB Guessed the password with 298 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Guessed the password with 115 queries.
2 Correct 2 ms 256 KB Guessed the password with 178 queries.
3 Correct 1 ms 256 KB Guessed the password with 98 queries.
4 Correct 4 ms 256 KB Guessed the password with 370 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 376 KB Guessed the password with 7306 queries.
2 Correct 152 ms 376 KB Guessed the password with 11837 queries.
3 Correct 217 ms 504 KB Guessed the password with 19329 queries.
4 Correct 242 ms 632 KB Guessed the password with 21715 queries.

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Guessed the password with 130 queries.
2 Correct 4 ms 256 KB Guessed the password with 298 queries.
3 Correct 2 ms 256 KB Guessed the password with 115 queries.
4 Correct 2 ms 256 KB Guessed the password with 178 queries.
5 Correct 1 ms 256 KB Guessed the password with 98 queries.
6 Correct 4 ms 256 KB Guessed the password with 370 queries.
7 Correct 82 ms 376 KB Guessed the password with 7306 queries.
8 Correct 152 ms 376 KB Guessed the password with 11837 queries.
9 Correct 217 ms 504 KB Guessed the password with 19329 queries.
10 Correct 242 ms 632 KB Guessed the password with 21715 queries.
11 Correct 423 ms 636 KB Guessed the password with 49257 queries.
12 Correct 365 ms 392 KB Guessed the password with 42581 queries.
13 Correct 467 ms 380 KB Guessed the password with 48233 queries.
14 Correct 530 ms 508 KB Guessed the password with 44657 queries.
15 Correct 475 ms 508 KB Guessed the password with 48988 queries.
16 Correct 405 ms 512 KB Guessed the password with 45492 queries.
17 Incorrect 464 ms 508 KB Could not guess the password with 50000 queries.
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Guessed the password with 130 queries.
2 Correct 4 ms 256 KB Guessed the password with 298 queries.
3 Correct 2 ms 256 KB Guessed the password with 115 queries.
4 Correct 2 ms 256 KB Guessed the password with 178 queries.
5 Correct 1 ms 256 KB Guessed the password with 98 queries.
6 Correct 4 ms 256 KB Guessed the password with 370 queries.
7 Correct 82 ms 376 KB Guessed the password with 7306 queries.
8 Correct 152 ms 376 KB Guessed the password with 11837 queries.
9 Correct 217 ms 504 KB Guessed the password with 19329 queries.
10 Correct 242 ms 632 KB Guessed the password with 21715 queries.
11 Correct 423 ms 636 KB Guessed the password with 49257 queries.
12 Correct 365 ms 392 KB Guessed the password with 42581 queries.
13 Correct 467 ms 380 KB Guessed the password with 48233 queries.
14 Correct 530 ms 508 KB Guessed the password with 44657 queries.
15 Correct 475 ms 508 KB Guessed the password with 48988 queries.
16 Correct 405 ms 512 KB Guessed the password with 45492 queries.
17 Incorrect 464 ms 508 KB Could not guess the password with 50000 queries.
18 Halted 0 ms 0 KB -