oj.uz

Submission #332523

# Submission time Handle Problem Language Result Execution time Memory
332523 2020-12-02T19:05:14 Z xt0r3 Password (RMI18_password) C++14
40 / 100
 109 ms 636 KB 
#include<bits/stdc++.h>
using namespace std;

int query(string str);

string merge(vector<string>& sol, int lo, int hi){
	if(lo == hi) return sol[lo];
	int mi = (lo + hi) / 2;
	string s1 = merge(sol, lo, mi);
	string s2 = merge(sol, mi + 1, hi);
	int curr = 0, dex = 0;
	string res = "";
	while(curr < (int)s1.size() && dex < (int)s2.size()){
		string tmp = res + s2[dex] + s1.substr(curr);
		int kene = res.size() + s1.size() - curr + 1;
		if(query(tmp) == kene){
			res += s2[dex++];
		}
		else{
            res += s1[curr++];
		}
	}
	if(curr < (int)s1.size()) res += s1.substr(curr);
	if(dex < (int)s2.size()) res += s2.substr(dex);
	return res;
}

string guess(int n, int s){
	vector<string> sol(s, "");
	for(int i = 0; i < s; i++){
		do{
			string ss = "a";
			ss[0] += i;
			sol[i] += ss;
		}while(query(sol[i]) == (int)sol[i].size());
		sol[i] = sol[i].substr(0, (int)sol[i].size() - 1);
	}
	return merge(sol, 0, s - 1);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 75 queries.
2 Runtime error 1 ms 364 KB Execution killed with signal 13 (could be triggered by violating memory limits)

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 98 queries.
2 Correct 2 ms 364 KB Guessed the password with 186 queries.
3 Correct 3 ms 364 KB Guessed the password with 181 queries.
4 Correct 4 ms 364 KB Guessed the password with 298 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 364 KB Guessed the password with 4455 queries.
2 Correct 66 ms 620 KB Guessed the password with 6324 queries.
3 Correct 105 ms 492 KB Guessed the password with 7953 queries.
4 Correct 109 ms 636 KB Guessed the password with 10694 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 75 queries.
2 Runtime error 1 ms 364 KB Execution killed with signal 13 (could be triggered by violating memory limits)

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 75 queries.
2 Runtime error 1 ms 364 KB Execution killed with signal 13 (could be triggered by violating memory limits)