oj.uz

Submission #197669

# Submission time Handle Problem Language Result Execution time Memory
197669 2020-01-22T07:09:26 Z Sakamotoo Type Printer (IOI08_printer) C++14
100 / 100
 248 ms 119840 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
 
#define mp make_pair
#define fi first
#define se second
 
//mt19937 rng(time(NULL)); //int
mt19937_64 rng(time(NULL)); //Long Long
//shuffle(a.begin(),a.end(),rng); //shuffle
//rng(); //random
 
struct node{
	node *c[30];
	int val=0;
	int awal=0;
	node *b;
	int cnt=0;
	int maxi=0;
};
 
node *root= new node;
 
void ins(string s){
	node *now=root;
	for(int i=0; i<s.size(); i++){
		int ind=s[i]-'a'+1;
		if(now->c[ind]==NULL){
			now->c[ind]=new node;
			now->c[ind]->b=now;
		}
		now=now->c[ind];
		now->val=1;
		now->maxi=max(now->maxi,(int)s.size()-i);
	}
	now->cnt++;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n;
	cin>>n;
	root->awal=1;
	for(int i=1; i<=n; i++){
		string s;
		cin>>s;
		ins(s);
	}
	int pri=0;
	node *now=root;
	vector<char> v; 
	while(true){
		int ind=0;
		int lol=1e9;
		for(int i=1; i<=26; i++){
			if(now->c[i]==NULL){
				
			}else if(now->c[i]->val>0&&now->c[i]->maxi<lol){
				ind=i;
				lol=now->c[i]->maxi;
			}
		}
		if(now->cnt>0){
			now->cnt--;
			v.push_back('P');
			pri++;
		}else if(ind==0){
			v.push_back('-');
			now=now->b;
		}else {
			v.push_back('a'+ind-1);
			now=now->c[ind];
			now->val--;
		}
		if(pri==n) break; 
	}
	cout<<v.size()<<endl;
	for(int i=0; i<v.size(); i++){
		printf("%c\n",v[i]);
	}
}

Compilation message

printer.cpp: In function 'void ins(std::__cxx11::string)':
printer.cpp:31:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s.size(); i++){
               ~^~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 372 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 4 ms 1272 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7204 KB Output is correct
2 Correct 31 ms 15096 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 44016 KB Output is correct
2 Correct 209 ms 100712 KB Output is correct
3 Correct 117 ms 51700 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 34436 KB Output is correct
2 Correct 248 ms 119840 KB Output is correct
3 Correct 129 ms 58736 KB Output is correct
4 Correct 224 ms 113256 KB Output is correct