oj.uz

Submission #65047

# Submission time Handle Problem Language Result Execution time Memory
65047 2018-08-06T13:46:07 Z TuGSGeReL Type Printer (IOI08_printer) C++14
100 / 100
 329 ms 113172 KB 
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back
#define ss second
#define ff first
#define ext exit(0)
using namespace std;
struct trie{
	trie *next[26];
	ll h,door;
	trie(){
		for(int i=0;i<26;i++) next[i]=NULL;
		h=-1;
		door=0;
	}
};
ll n,zr[26];
string s[111111];
vector<pair<ll,ll> >v;
vector<char>ans;
void insert(trie *root,string s){
	for(int i=0;i<s.size();i++){
		if(root->next[s[i]-'a']==NULL){
			root->next[s[i]-'a']=new trie();
		}
		root=root->next[s[i]-'a'];
		ll oo=s.size()-i-1;
		root->door=max(oo,root->door);
	}
	root->h=1;
}
void nem(trie* root){
	if(root->h==1) ans.pub('P');
	vector<pair<ll,ll> >kkkk;
	for(int i=0;i<26;i++){
		if(root->next[i]!=NULL){
			kkkk.pub(mp(root->next[i]->door,i));
		}
	}
	sort(kkkk.begin(),kkkk.end());
	for(int i=0;i<kkkk.size();i++) {
		ans.pub(kkkk[i].ss+'a');
		nem(root->next[kkkk[i].ss]);
		ans.pub('-');
	}
}
void solv(ll k,trie *root){
	root=root->next[k];
	ans.pub(char(k+'a'));
	nem(root);
}
int main (){
	trie *root=new trie();
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		ll oo=s[i].size();
		zr[s[i][0]-'a']=max(zr[s[i][0]-'a'],oo);
		insert(root,s[i]);
	}
	for(int i=0;i<26;i++) v.pub(mp(zr[i],i));
	sort(v.begin(),v.end());
	for(int i=0;i<26;i++){
		if(v[i].ff)solv(v[i].ss,root),ans.pub('-');
	}
	while(ans.back()=='-') ans.pop_back();
	cout<<ans.size()<<"\n";
	for(int i=0;i<ans.size();i++){
		cout<<ans[i]<<"\n";
	}
}

Compilation message

printer.cpp: In function 'void insert(trie*, std::__cxx11::string)':
printer.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++){
              ~^~~~~~~~~
printer.cpp: In function 'void nem(trie*)':
printer.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<kkkk.size();i++) {
              ~^~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ans.size();i++){
              ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3832 KB Output is correct
2 Correct 6 ms 3832 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3900 KB Output is correct
2 Correct 6 ms 3904 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3932 KB Output is correct
2 Correct 8 ms 4032 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4032 KB Output is correct
2 Correct 7 ms 4148 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4264 KB Output is correct
2 Correct 11 ms 5040 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5816 KB Output is correct
2 Correct 12 ms 6228 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10224 KB Output is correct
2 Correct 52 ms 17444 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 19876 KB Output is correct
2 Correct 34 ms 19876 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 43676 KB Output is correct
2 Correct 276 ms 95012 KB Output is correct
3 Correct 154 ms 95012 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 95012 KB Output is correct
2 Correct 329 ms 113172 KB Output is correct
3 Correct 155 ms 113172 KB Output is correct
4 Correct 275 ms 113172 KB Output is correct