oj.uz

Submission #342342

# Submission time Handle Problem Language Result Execution time Memory
342342 2021-01-01T23:01:32 Z Gajowy Password (RMI18_password) C++14
80 / 100
 967 ms 772 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string str);

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;
			for(int l=1;l<=qres;l++){
				int lo=0,hi=res.size();
				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<l;i++)
						qs.push_back(c);
					int smqres=query(qs);
					if(smqres==(int)qs.size())
						lo=mid;
					else
						hi=mid-1;
				}
				pos.push_back(lo);
			}
			reverse(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 1 ms 364 KB Guessed the password with 101 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Guessed the password with 116 queries.
2 Correct 1 ms 364 KB Guessed the password with 132 queries.
3 Correct 1 ms 364 KB Guessed the password with 75 queries.
4 Correct 4 ms 364 KB Guessed the password with 337 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 380 KB Guessed the password with 6927 queries.
2 Correct 90 ms 380 KB Guessed the password with 10986 queries.
3 Correct 180 ms 364 KB Guessed the password with 11895 queries.
4 Correct 263 ms 364 KB Guessed the password with 17681 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 1 ms 364 KB Guessed the password with 101 queries.
3 Correct 2 ms 364 KB Guessed the password with 116 queries.
4 Correct 1 ms 364 KB Guessed the password with 132 queries.
5 Correct 1 ms 364 KB Guessed the password with 75 queries.
6 Correct 4 ms 364 KB Guessed the password with 337 queries.
7 Correct 54 ms 380 KB Guessed the password with 6927 queries.
8 Correct 90 ms 380 KB Guessed the password with 10986 queries.
9 Correct 180 ms 364 KB Guessed the password with 11895 queries.
10 Correct 263 ms 364 KB Guessed the password with 17681 queries.
11 Correct 401 ms 556 KB Guessed the password with 22729 queries.
12 Correct 350 ms 540 KB Guessed the password with 22601 queries.
13 Correct 421 ms 516 KB Guessed the password with 27496 queries.
14 Correct 467 ms 424 KB Guessed the password with 27484 queries.
15 Correct 496 ms 364 KB Guessed the password with 28381 queries.
16 Correct 494 ms 420 KB Guessed the password with 28380 queries.
17 Correct 452 ms 636 KB Guessed the password with 28220 queries.
18 Correct 499 ms 492 KB Guessed the password with 28469 queries.
19 Correct 500 ms 492 KB Guessed the password with 27687 queries.
20 Correct 479 ms 548 KB Guessed the password with 27969 queries.
21 Correct 563 ms 624 KB Guessed the password with 31261 queries.
22 Correct 640 ms 420 KB Guessed the password with 31122 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Guessed the password with 59 queries.
2 Correct 1 ms 364 KB Guessed the password with 101 queries.
3 Correct 2 ms 364 KB Guessed the password with 116 queries.
4 Correct 1 ms 364 KB Guessed the password with 132 queries.
5 Correct 1 ms 364 KB Guessed the password with 75 queries.
6 Correct 4 ms 364 KB Guessed the password with 337 queries.
7 Correct 54 ms 380 KB Guessed the password with 6927 queries.
8 Correct 90 ms 380 KB Guessed the password with 10986 queries.
9 Correct 180 ms 364 KB Guessed the password with 11895 queries.
10 Correct 263 ms 364 KB Guessed the password with 17681 queries.
11 Correct 401 ms 556 KB Guessed the password with 22729 queries.
12 Correct 350 ms 540 KB Guessed the password with 22601 queries.
13 Correct 421 ms 516 KB Guessed the password with 27496 queries.
14 Correct 467 ms 424 KB Guessed the password with 27484 queries.
15 Correct 496 ms 364 KB Guessed the password with 28381 queries.
16 Correct 494 ms 420 KB Guessed the password with 28380 queries.
17 Correct 452 ms 636 KB Guessed the password with 28220 queries.
18 Correct 499 ms 492 KB Guessed the password with 28469 queries.
19 Correct 500 ms 492 KB Guessed the password with 27687 queries.
20 Correct 479 ms 548 KB Guessed the password with 27969 queries.
21 Correct 563 ms 624 KB Guessed the password with 31261 queries.
22 Correct 640 ms 420 KB Guessed the password with 31122 queries.
23 Incorrect 967 ms 772 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -