oj.uz

Submission #342346

# Submission time Handle Problem Language Result Execution time Memory
342346 2021-01-01T23:22:57 Z Gajowy Password (RMI18_password) C++14
100 / 100
 473 ms 872 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string str);

void solve_positions(char c,string &res,int l,int r,int pl,int pr,vector<int> &resvec){
	int len=(l+r)/2;
	int lo=pl,hi=pr;
	string qs;
	while(lo<hi){
		qs.clear();
		int mid=(lo+hi)/2+1;
		for(int i=0;i<mid;i++)
			qs.push_back(res[i]);
		for(int i=0;i<len;i++)
			qs.push_back(c);
		int smqres=query(qs);
		if(smqres==(int)qs.size())
			lo=mid;
		else
			hi=mid-1;
	}
	resvec.push_back(lo);
	if(len-1>=l)
		solve_positions(c,res,l,len-1,lo,pr,resvec);
	if(len+1<=r)
		solve_positions(c,res,len+1,r,pl,lo,resvec);
}

string guess(int n,int s){
	string res;
	string qs;
	vector<int> cnts(s);
	for(int cc=0;cc<s;cc++){
		char c=(char)('a'+cc);
		qs.clear();
		for(int i=0;i<n;i++)
			qs.push_back(c);
		int qres=query(qs);
		cnts[cc]=qres;
	}
	vector<pair<int,int>> srt;
	for(int i=0;i<s;i++)
		srt.push_back(make_pair(cnts[i],i));
	sort(begin(srt),end(srt),greater<pair<int,int>>());
	for(int cc=0;cc<s;cc++){
		char c=(char)('a'+srt[cc].second);
		int maxcount=srt[cc].first;
		qs.clear();
		if(res.size()==0){
			int qres=maxcount;
			for(int i=0;i<qres;i++)
				res.push_back(c);
		}
		else
		if((int)res.size()<n){
			int qres=maxcount;
			if(qres==0)
				continue;
			vector<int> pos;
			solve_positions(c,res,1,qres,0,res.size(),pos);
			sort(begin(pos),end(pos));
			string new_res;
			for(int i=res.size();i>=0;i--){
				while(pos.size()>0&&pos.back()>=i)
					new_res.push_back(c),pos.pop_back();
				if(i!=0)
					new_res.push_back(res[i-1]);
			}
			reverse(begin(new_res),end(new_res));
			res=new_res;
		}
	}
	return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 59 queries.
2 Correct 2 ms 364 KB Guessed the password with 101 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 45 queries.
2 Correct 1 ms 364 KB Guessed the password with 86 queries.
3 Correct 1 ms 364 KB Guessed the password with 39 queries.
4 Correct 2 ms 384 KB Guessed the password with 180 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 364 KB Guessed the password with 2563 queries.
2 Correct 54 ms 652 KB Guessed the password with 3201 queries.
3 Correct 69 ms 496 KB Guessed the password with 4877 queries.
4 Correct 101 ms 492 KB Guessed the password with 7166 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 59 queries.
2 Correct 2 ms 364 KB Guessed the password with 101 queries.
3 Correct 1 ms 364 KB Guessed the password with 45 queries.
4 Correct 1 ms 364 KB Guessed the password with 86 queries.
5 Correct 1 ms 364 KB Guessed the password with 39 queries.
6 Correct 2 ms 384 KB Guessed the password with 180 queries.
7 Correct 36 ms 364 KB Guessed the password with 2563 queries.
8 Correct 54 ms 652 KB Guessed the password with 3201 queries.
9 Correct 69 ms 496 KB Guessed the password with 4877 queries.
10 Correct 101 ms 492 KB Guessed the password with 7166 queries.
11 Correct 111 ms 388 KB Guessed the password with 8627 queries.
12 Correct 133 ms 656 KB Guessed the password with 8646 queries.
13 Correct 187 ms 536 KB Guessed the password with 10476 queries.
14 Correct 175 ms 700 KB Guessed the password with 10496 queries.
15 Correct 186 ms 620 KB Guessed the password with 11299 queries.
16 Correct 213 ms 492 KB Guessed the password with 11308 queries.
17 Correct 188 ms 364 KB Guessed the password with 9888 queries.
18 Correct 182 ms 364 KB Guessed the password with 9724 queries.
19 Correct 194 ms 492 KB Guessed the password with 10203 queries.
20 Correct 183 ms 364 KB Guessed the password with 10347 queries.
21 Correct 105 ms 492 KB Guessed the password with 6688 queries.
22 Correct 141 ms 364 KB Guessed the password with 6450 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 59 queries.
2 Correct 2 ms 364 KB Guessed the password with 101 queries.
3 Correct 1 ms 364 KB Guessed the password with 45 queries.
4 Correct 1 ms 364 KB Guessed the password with 86 queries.
5 Correct 1 ms 364 KB Guessed the password with 39 queries.
6 Correct 2 ms 384 KB Guessed the password with 180 queries.
7 Correct 36 ms 364 KB Guessed the password with 2563 queries.
8 Correct 54 ms 652 KB Guessed the password with 3201 queries.
9 Correct 69 ms 496 KB Guessed the password with 4877 queries.
10 Correct 101 ms 492 KB Guessed the password with 7166 queries.
11 Correct 111 ms 388 KB Guessed the password with 8627 queries.
12 Correct 133 ms 656 KB Guessed the password with 8646 queries.
13 Correct 187 ms 536 KB Guessed the password with 10476 queries.
14 Correct 175 ms 700 KB Guessed the password with 10496 queries.
15 Correct 186 ms 620 KB Guessed the password with 11299 queries.
16 Correct 213 ms 492 KB Guessed the password with 11308 queries.
17 Correct 188 ms 364 KB Guessed the password with 9888 queries.
18 Correct 182 ms 364 KB Guessed the password with 9724 queries.
19 Correct 194 ms 492 KB Guessed the password with 10203 queries.
20 Correct 183 ms 364 KB Guessed the password with 10347 queries.
21 Correct 105 ms 492 KB Guessed the password with 6688 queries.
22 Correct 141 ms 364 KB Guessed the password with 6450 queries.
23 Correct 255 ms 520 KB Guessed the password with 13318 queries.
24 Correct 251 ms 708 KB Guessed the password with 11506 queries.
25 Correct 431 ms 872 KB Guessed the password with 21076 queries.
26 Correct 361 ms 836 KB Guessed the password with 17146 queries.
27 Correct 473 ms 772 KB Guessed the password with 23436 queries.
28 Correct 332 ms 592 KB Guessed the password with 16827 queries.
29 Correct 464 ms 856 KB Guessed the password with 25045 queries.
30 Correct 348 ms 716 KB Guessed the password with 15436 queries.