oj.uz

Submission #201083

# Submission time Handle Problem Language Result Execution time Memory
201083 2020-02-09T10:00:11 Z etaha Password (RMI18_password) C++14
100 / 100
 754 ms 672 KB 
#include<bits/stdc++.h>
using namespace std;
#define mods 1000000007
#define pb push_back
#define mp make_pair
#define st first
#define nd second
typedef long long int lint;
typedef unsigned long long int ulint;
typedef pair<lint,lint> pii;

int query(string q);
int dizi[30];

string sifre="";
string ekle(string s,char c,int ind){
	int i;
	string ret;
	for(i=0;i<ind;i++) ret+=s[i];
	ret+=c;
	for(;i<s.size();i++) ret+=s[i];
	//cout<<c<<" "<<ret<<" "<<query(ret)<<endl;
	return ret;


}

string merge(int l,int r){
	int i,j,k;
	string ret;
	if(l==r){
		for(i=0;i<dizi[l];i++) ret+='a'+l;
		return ret;
	}else{
		string cev1,cev2;
		int m=l+(r-l)/2;
		cev1=merge(l,m);
		cev2=merge(m+1,r);
		//cout<<cev1<<" "<<cev2<<endl;
		int son=0;
		for(j=0;j<=cev1.size() && son<cev2.size();j++){
			if(query(ekle(cev1,cev2[son],j))==cev1.size()+1) cev1=ekle(cev1,cev2[son],j), son++;
		}
		return cev1;	
	}
}
string guess(int n,int s){
	int i,j,k;

	int ek=0,son=1;
	for(j=0;j<s;j++){
		string a;
		for(i=0;i<n;i++) a+='a'+j;
		dizi[j]=query(a);
		if(dizi[j]==n) return a;
		//cout<<(char)('a'+j)<<" "<<dizi[j]<<endl;
	}
	sifre=merge(0,s-1);
//	int temp=query(sifre);
	//cout<<sifre<<endl;
	//cout<<temp<<endl;
	return sifre;


}

Compilation message

password.cpp: In function 'std::__cxx11::string ekle(std::__cxx11::string, char, int)':
password.cpp:21:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(;i<s.size();i++) ret+=s[i];
       ~^~~~~~~~~
password.cpp: In function 'std::__cxx11::string merge(int, int)':
password.cpp:41:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<=cev1.size() && son<cev2.size();j++){
           ~^~~~~~~~~~~~~
password.cpp:41:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<=cev1.size() && son<cev2.size();j++){
                             ~~~^~~~~~~~~~~~
password.cpp:42:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(query(ekle(cev1,cev2[son],j))==cev1.size()+1) cev1=ekle(cev1,cev2[son],j), son++;
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
password.cpp:29:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k;
          ^
password.cpp: In function 'std::__cxx11::string guess(int, int)':
password.cpp:48:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k;
          ^
password.cpp:50:6: warning: unused variable 'ek' [-Wunused-variable]
  int ek=0,son=1;
      ^~
password.cpp:50:11: warning: unused variable 'son' [-Wunused-variable]
  int ek=0,son=1;
           ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Guessed the password with 68 queries.
2 Correct 6 ms 248 KB Guessed the password with 111 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Guessed the password with 48 queries.
2 Correct 6 ms 248 KB Guessed the password with 116 queries.
3 Correct 6 ms 248 KB Guessed the password with 93 queries.
4 Correct 7 ms 248 KB Guessed the password with 203 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 248 KB Guessed the password with 3704 queries.
2 Correct 84 ms 376 KB Guessed the password with 5053 queries.
3 Correct 110 ms 248 KB Guessed the password with 6584 queries.
4 Correct 156 ms 248 KB Guessed the password with 8721 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Guessed the password with 68 queries.
2 Correct 6 ms 248 KB Guessed the password with 111 queries.
3 Correct 5 ms 248 KB Guessed the password with 48 queries.
4 Correct 6 ms 248 KB Guessed the password with 116 queries.
5 Correct 6 ms 248 KB Guessed the password with 93 queries.
6 Correct 7 ms 248 KB Guessed the password with 203 queries.
7 Correct 63 ms 248 KB Guessed the password with 3704 queries.
8 Correct 84 ms 376 KB Guessed the password with 5053 queries.
9 Correct 110 ms 248 KB Guessed the password with 6584 queries.
10 Correct 156 ms 248 KB Guessed the password with 8721 queries.
11 Correct 365 ms 380 KB Guessed the password with 13682 queries.
12 Correct 326 ms 248 KB Guessed the password with 12654 queries.
13 Correct 347 ms 248 KB Guessed the password with 14410 queries.
14 Correct 335 ms 504 KB Guessed the password with 13979 queries.
15 Correct 376 ms 376 KB Guessed the password with 15314 queries.
16 Correct 376 ms 504 KB Guessed the password with 14485 queries.
17 Correct 488 ms 376 KB Guessed the password with 16114 queries.
18 Correct 420 ms 376 KB Guessed the password with 15294 queries.
19 Correct 497 ms 504 KB Guessed the password with 16485 queries.
20 Correct 441 ms 380 KB Guessed the password with 15088 queries.
21 Correct 496 ms 376 KB Guessed the password with 16990 queries.
22 Correct 471 ms 504 KB Guessed the password with 15908 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Guessed the password with 68 queries.
2 Correct 6 ms 248 KB Guessed the password with 111 queries.
3 Correct 5 ms 248 KB Guessed the password with 48 queries.
4 Correct 6 ms 248 KB Guessed the password with 116 queries.
5 Correct 6 ms 248 KB Guessed the password with 93 queries.
6 Correct 7 ms 248 KB Guessed the password with 203 queries.
7 Correct 63 ms 248 KB Guessed the password with 3704 queries.
8 Correct 84 ms 376 KB Guessed the password with 5053 queries.
9 Correct 110 ms 248 KB Guessed the password with 6584 queries.
10 Correct 156 ms 248 KB Guessed the password with 8721 queries.
11 Correct 365 ms 380 KB Guessed the password with 13682 queries.
12 Correct 326 ms 248 KB Guessed the password with 12654 queries.
13 Correct 347 ms 248 KB Guessed the password with 14410 queries.
14 Correct 335 ms 504 KB Guessed the password with 13979 queries.
15 Correct 376 ms 376 KB Guessed the password with 15314 queries.
16 Correct 376 ms 504 KB Guessed the password with 14485 queries.
17 Correct 488 ms 376 KB Guessed the password with 16114 queries.
18 Correct 420 ms 376 KB Guessed the password with 15294 queries.
19 Correct 497 ms 504 KB Guessed the password with 16485 queries.
20 Correct 441 ms 380 KB Guessed the password with 15088 queries.
21 Correct 496 ms 376 KB Guessed the password with 16990 queries.
22 Correct 471 ms 504 KB Guessed the password with 15908 queries.
23 Correct 648 ms 652 KB Guessed the password with 23708 queries.
24 Correct 653 ms 660 KB Guessed the password with 22770 queries.
25 Correct 662 ms 632 KB Guessed the password with 23853 queries.
26 Correct 754 ms 672 KB Guessed the password with 23374 queries.
27 Correct 643 ms 664 KB Guessed the password with 23807 queries.
28 Correct 665 ms 640 KB Guessed the password with 23436 queries.
29 Correct 665 ms 656 KB Guessed the password with 23873 queries.
30 Correct 694 ms 544 KB Guessed the password with 23818 queries.