Submission #260362

#	Time	Username	Problem	Language	Result	Execution time	Memory
260362		dvdg6566	Password (RMI18_password)	C++14	100 / 100	374 ms	768 KiB

password

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20