oj.uz

답안 #286979

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
286979 2020-08-31T08:22:48 Z crossing0ver Password (RMI18_password) C++17
50 / 100
 553 ms 504 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 256 KB Guessed the password with 142 queries.
2 Correct 3 ms 256 KB Guessed the password with 294 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Guessed the password with 120 queries.
2 Correct 2 ms 256 KB Guessed the password with 243 queries.
3 Correct 2 ms 256 KB Guessed the password with 92 queries.
4 Correct 4 ms 256 KB Guessed the password with 323 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 384 KB Guessed the password with 5922 queries.
2 Correct 108 ms 504 KB Guessed the password with 11863 queries.
3 Correct 134 ms 504 KB Guessed the password with 17186 queries.
4 Correct 252 ms 376 KB Guessed the password with 24260 queries.

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Guessed the password with 142 queries.
2 Correct 3 ms 256 KB Guessed the password with 294 queries.
3 Correct 2 ms 256 KB Guessed the password with 120 queries.
4 Correct 2 ms 256 KB Guessed the password with 243 queries.
5 Correct 2 ms 256 KB Guessed the password with 92 queries.
6 Correct 4 ms 256 KB Guessed the password with 323 queries.
7 Correct 66 ms 384 KB Guessed the password with 5922 queries.
8 Correct 108 ms 504 KB Guessed the password with 11863 queries.
9 Correct 134 ms 504 KB Guessed the password with 17186 queries.
10 Correct 252 ms 376 KB Guessed the password with 24260 queries.
11 Correct 263 ms 384 KB Guessed the password with 34841 queries.
12 Incorrect 553 ms 504 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Guessed the password with 142 queries.
2 Correct 3 ms 256 KB Guessed the password with 294 queries.
3 Correct 2 ms 256 KB Guessed the password with 120 queries.
4 Correct 2 ms 256 KB Guessed the password with 243 queries.
5 Correct 2 ms 256 KB Guessed the password with 92 queries.
6 Correct 4 ms 256 KB Guessed the password with 323 queries.
7 Correct 66 ms 384 KB Guessed the password with 5922 queries.
8 Correct 108 ms 504 KB Guessed the password with 11863 queries.
9 Correct 134 ms 504 KB Guessed the password with 17186 queries.
10 Correct 252 ms 376 KB Guessed the password with 24260 queries.
11 Correct 263 ms 384 KB Guessed the password with 34841 queries.
12 Incorrect 553 ms 504 KB Could not guess the password with 50000 queries.
13 Halted 0 ms 0 KB -