oj.uz

Submission #251376

# Submission time Handle Problem Language Result Execution time Memory
251376 2020-07-21T04:45:06 Z jamielim Password (RMI18_password) C++14
100 / 100
 482 ms 704 KB 
// Sample grader for contestants' use.
//
// Usage: place your input data in the file password.in in the format
//
// line 1: N S
// line 2: hidden_password
//
// Then compile this grader together with your implementation.
// Run the binary to see your guessing strategy at work!
// Set DEBUG to 1 to print all queries.
#include <bits/stdc++.h>
using namespace std;
int query(string q);
#define fi first
#define se second
#define pb push_back
#define mp make_pair

/*
map<string,int> ma;
int qry(string q){
	if(ma.find(q)!=ma.end())return ma[q];
	return ma[q]=query(q);
}
*/

string join(string a,string b){
	int la=a.length(),lb=b.length();
	string ans=a;
	int idx=0;
	for(int i=0;i<lb;i++){
		string q="";
		for(int j=0;j<idx;j++)q.pb(ans[j]);
		q.pb(b[i]);
		for(int j=idx;j<(int)ans.size();j++)q.pb(ans[j]);
		while(query(q)!=(int)q.size()){
			swap(q[idx],q[idx+1]);
			idx++;
		}
		ans=q;idx++;
	}
	return ans;
}

string guess(int n, int s){
	priority_queue<pair<int,string>,vector<pair<int,string> >,greater<pair<int,string> > > pq;
	int occ[26];
	int sum=0;
	for(int i=0;i<s-1;i++){
		string q="";
		for(int j=0;j<n;j++)q.pb(i+'a');
		occ[i]=query(q);
		q="";
		for(int j=0;j<occ[i];j++)q.pb(i+'a');
		if(occ[i]>0)pq.push(mp(occ[i],q));
		sum+=occ[i];
	}
	occ[s-1]=n-sum;
	string q="";for(int j=0;j<occ[s-1];j++)q.pb(s-1+'a');if(occ[s-1]>0)pq.push(mp(occ[s-1],q));
	while((int)pq.size()>1){
		pair<int,string> cur1=pq.top();pq.pop();
		pair<int,string> cur2=pq.top();pq.pop();
		pq.push(mp(cur1.fi+cur2.fi,join(cur1.se,cur2.se)));
	}
	return pq.top().se;
}

Compilation message

password.cpp: In function 'std::__cxx11::string join(std::__cxx11::string, std::__cxx11::string)':
password.cpp:28:6: warning: unused variable 'la' [-Wunused-variable]
  int la=a.length(),lb=b.length();
      ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Guessed the password with 61 queries.
2 Correct 2 ms 256 KB Guessed the password with 120 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 47 queries.
2 Correct 2 ms 256 KB Guessed the password with 92 queries.
3 Correct 1 ms 256 KB Guessed the password with 90 queries.
4 Correct 3 ms 256 KB Guessed the password with 179 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 376 KB Guessed the password with 2760 queries.
2 Correct 75 ms 384 KB Guessed the password with 5103 queries.
3 Correct 74 ms 376 KB Guessed the password with 4604 queries.
4 Correct 110 ms 504 KB Guessed the password with 8100 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Guessed the password with 61 queries.
2 Correct 2 ms 256 KB Guessed the password with 120 queries.
3 Correct 1 ms 256 KB Guessed the password with 47 queries.
4 Correct 2 ms 256 KB Guessed the password with 92 queries.
5 Correct 1 ms 256 KB Guessed the password with 90 queries.
6 Correct 3 ms 256 KB Guessed the password with 179 queries.
7 Correct 42 ms 376 KB Guessed the password with 2760 queries.
8 Correct 75 ms 384 KB Guessed the password with 5103 queries.
9 Correct 74 ms 376 KB Guessed the password with 4604 queries.
10 Correct 110 ms 504 KB Guessed the password with 8100 queries.
11 Correct 120 ms 628 KB Guessed the password with 8177 queries.
12 Correct 109 ms 384 KB Guessed the password with 8183 queries.
13 Correct 177 ms 384 KB Guessed the password with 11548 queries.
14 Correct 182 ms 504 KB Guessed the password with 11678 queries.
15 Correct 168 ms 632 KB Guessed the password with 10909 queries.
16 Correct 176 ms 504 KB Guessed the password with 10879 queries.
17 Correct 175 ms 504 KB Guessed the password with 10244 queries.
18 Correct 180 ms 504 KB Guessed the password with 10273 queries.
19 Correct 197 ms 384 KB Guessed the password with 9708 queries.
20 Correct 183 ms 384 KB Guessed the password with 9800 queries.
21 Correct 174 ms 504 KB Guessed the password with 11742 queries.
22 Correct 190 ms 384 KB Guessed the password with 11780 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Guessed the password with 61 queries.
2 Correct 2 ms 256 KB Guessed the password with 120 queries.
3 Correct 1 ms 256 KB Guessed the password with 47 queries.
4 Correct 2 ms 256 KB Guessed the password with 92 queries.
5 Correct 1 ms 256 KB Guessed the password with 90 queries.
6 Correct 3 ms 256 KB Guessed the password with 179 queries.
7 Correct 42 ms 376 KB Guessed the password with 2760 queries.
8 Correct 75 ms 384 KB Guessed the password with 5103 queries.
9 Correct 74 ms 376 KB Guessed the password with 4604 queries.
10 Correct 110 ms 504 KB Guessed the password with 8100 queries.
11 Correct 120 ms 628 KB Guessed the password with 8177 queries.
12 Correct 109 ms 384 KB Guessed the password with 8183 queries.
13 Correct 177 ms 384 KB Guessed the password with 11548 queries.
14 Correct 182 ms 504 KB Guessed the password with 11678 queries.
15 Correct 168 ms 632 KB Guessed the password with 10909 queries.
16 Correct 176 ms 504 KB Guessed the password with 10879 queries.
17 Correct 175 ms 504 KB Guessed the password with 10244 queries.
18 Correct 180 ms 504 KB Guessed the password with 10273 queries.
19 Correct 197 ms 384 KB Guessed the password with 9708 queries.
20 Correct 183 ms 384 KB Guessed the password with 9800 queries.
21 Correct 174 ms 504 KB Guessed the password with 11742 queries.
22 Correct 190 ms 384 KB Guessed the password with 11780 queries.
23 Correct 417 ms 532 KB Guessed the password with 23750 queries.
24 Correct 381 ms 408 KB Guessed the password with 21004 queries.
25 Correct 482 ms 452 KB Guessed the password with 23740 queries.
26 Correct 361 ms 408 KB Guessed the password with 19117 queries.
27 Correct 403 ms 516 KB Guessed the password with 23711 queries.
28 Correct 326 ms 404 KB Guessed the password with 16851 queries.
29 Correct 400 ms 540 KB Guessed the password with 23731 queries.
30 Correct 279 ms 704 KB Guessed the password with 14419 queries.