oj.uz

Submission #260362

# Submission time Handle Problem Language Result Execution time Memory
260362 2020-08-10T07:11:13 Z dvdg6566 Password (RMI18_password) C++14
100 / 100
 374 ms 768 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5001;

int query(string str);

int occ[26];
string res="";

int cmp(int a,int b){
	if(a==-1&&b==-1)return -1;
	if(a==-1)return b;
	if(b==-1)return a;
	string cons=res;
	cons+=(char)('a'+b);
	for(int i=0;i<occ[a];++i)cons+=(char)('a'+a);
	// cerr<<cons<<'\n';
	if(query(cons) == cons.size())return b;
	return a;
}

struct node{
	int s,e,m,v;
	node *l,*r;
	node(int _s,int _e):s(_s),e(_e){
		m=(s+e)/2;
		v=-1;
		if(s==e){
			if(occ[s])v=s;
		}else{
			l=new node(s,m);
			r=new node(m+1,e);
			v=cmp(l->v,r->v);
		}
	}
	void remove(int x){
		if(s==e){
			--occ[x];
			if(!occ[x])v=-1;
			else v=x;
			return;
		}
		if(x<=m)l->remove(x);
		else r->remove(x);
		v=cmp(l->v,r->v);
		// cerr<<s<<' '<<e<<' '<<v<<'\n';
	}
}*root;

string guess(int N,int S){
	for(int i=0;i<S;++i){
		string q="";
		while(1){
			q+=(char)(i+'a');
			int t=query(q);
			if(t==q.size())continue;
			else break;
		}
		q.pop_back();
		occ[i]=q.size();
	}
	root=new node(0,25);
	for(int i=0;i<N;++i){
		res+=('a'+root->v);
		root->remove(root->v);
		// cerr<<"Answer "<<res<<'\n';
	}
	return res;
}

Compilation message

password.cpp: In function 'int cmp(int, int)':
password.cpp:18:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(query(cons) == cons.size())return b;
     ~~~~~~~~~~~~^~~~~~~~~~~~~~
password.cpp: In function 'std::__cxx11::string guess(int, int)':
password.cpp:56:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(t==q.size())continue;
       ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 98 queries.
2 Correct 3 ms 256 KB Guessed the password with 186 queries.
3 Correct 3 ms 256 KB Guessed the password with 182 queries.
4 Correct 5 ms 384 KB Guessed the password with 298 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 376 KB Guessed the password with 4315 queries.
2 Correct 62 ms 256 KB Guessed the password with 6944 queries.
3 Correct 87 ms 376 KB Guessed the password with 8500 queries.
4 Correct 110 ms 376 KB Guessed the password with 10847 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 78 queries.
2 Correct 3 ms 384 KB Guessed the password with 128 queries.
3 Correct 2 ms 256 KB Guessed the password with 98 queries.
4 Correct 3 ms 256 KB Guessed the password with 186 queries.
5 Correct 3 ms 256 KB Guessed the password with 182 queries.
6 Correct 5 ms 384 KB Guessed the password with 298 queries.
7 Correct 62 ms 376 KB Guessed the password with 4315 queries.
8 Correct 62 ms 256 KB Guessed the password with 6944 queries.
9 Correct 87 ms 376 KB Guessed the password with 8500 queries.
10 Correct 110 ms 376 KB Guessed the password with 10847 queries.
11 Correct 214 ms 380 KB Guessed the password with 16438 queries.
12 Correct 213 ms 512 KB Guessed the password with 15260 queries.
13 Correct 148 ms 388 KB Guessed the password with 17392 queries.
14 Correct 172 ms 372 KB Guessed the password with 16938 queries.
15 Correct 246 ms 380 KB Guessed the password with 18272 queries.
16 Correct 227 ms 504 KB Guessed the password with 17353 queries.
17 Correct 264 ms 504 KB Guessed the password with 19353 queries.
18 Correct 181 ms 504 KB Guessed the password with 18490 queries.
19 Correct 219 ms 376 KB Guessed the password with 19810 queries.
20 Correct 293 ms 508 KB Guessed the password with 17648 queries.
21 Correct 243 ms 632 KB Guessed the password with 20348 queries.
22 Correct 218 ms 376 KB Guessed the password with 18816 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 78 queries.
2 Correct 3 ms 384 KB Guessed the password with 128 queries.
3 Correct 2 ms 256 KB Guessed the password with 98 queries.
4 Correct 3 ms 256 KB Guessed the password with 186 queries.
5 Correct 3 ms 256 KB Guessed the password with 182 queries.
6 Correct 5 ms 384 KB Guessed the password with 298 queries.
7 Correct 62 ms 376 KB Guessed the password with 4315 queries.
8 Correct 62 ms 256 KB Guessed the password with 6944 queries.
9 Correct 87 ms 376 KB Guessed the password with 8500 queries.
10 Correct 110 ms 376 KB Guessed the password with 10847 queries.
11 Correct 214 ms 380 KB Guessed the password with 16438 queries.
12 Correct 213 ms 512 KB Guessed the password with 15260 queries.
13 Correct 148 ms 388 KB Guessed the password with 17392 queries.
14 Correct 172 ms 372 KB Guessed the password with 16938 queries.
15 Correct 246 ms 380 KB Guessed the password with 18272 queries.
16 Correct 227 ms 504 KB Guessed the password with 17353 queries.
17 Correct 264 ms 504 KB Guessed the password with 19353 queries.
18 Correct 181 ms 504 KB Guessed the password with 18490 queries.
19 Correct 219 ms 376 KB Guessed the password with 19810 queries.
20 Correct 293 ms 508 KB Guessed the password with 17648 queries.
21 Correct 243 ms 632 KB Guessed the password with 20348 queries.
22 Correct 218 ms 376 KB Guessed the password with 18816 queries.
23 Correct 285 ms 640 KB Guessed the password with 28613 queries.
24 Correct 292 ms 664 KB Guessed the password with 27227 queries.
25 Correct 324 ms 664 KB Guessed the password with 28795 queries.
26 Correct 321 ms 768 KB Guessed the password with 28333 queries.
27 Correct 374 ms 512 KB Guessed the password with 28764 queries.
28 Correct 361 ms 688 KB Guessed the password with 28045 queries.
29 Correct 337 ms 588 KB Guessed the password with 28848 queries.
30 Correct 334 ms 648 KB Guessed the password with 27507 queries.