oj.uz

Submission #63240

# Submission time Handle Problem Language Result Execution time Memory
63240 2018-08-01T06:48:48 Z Tenuun Type Printer (IOI08_printer) C++17
100 / 100
 198 ms 108448 KB 
#include<bits/stdc++.h>
#define pb push_back
using namespace std;

string m;

struct node{
	char c;
	int val=0, mx=0;
	node *l[26];
	node(){
		for(int i=0; i<26; i++) {
			l[i]=NULL;
		}
	}
};

vector<char>res;

node *root=new node;

void insert(string s){
	node *now=root;
	int v;
	for(int i=0; i<s.length(); i++){
		v=s[i]-'a';
		if(now->l[v]==NULL){
			now->l[v]=new node;
			now->l[v]->c=s[i];
			now->l[v]->val++;
		}
		else{
			now->l[v]->val++;
		}
		now->mx++;
		now=now->l[v];
	}
}

void swp(){
	node *now=root;
	int ind=0;
	while(ind<m.length()){
		for(int i=0; i<26; i++){
			if(i==m[ind]-'a'){
				swap(now->l[25], now->l[i]);
				now=now->l[25];
				break;
			}
		}
		ind++;
	}
}

void print(node *now){
	int cnt=0;
	for(int i=0; i<26; i++){
		if(now->l[i]==NULL) continue;
		cnt++;
		res.pb(now->l[i]->c);
		//cout << now->l[i]->mx << " " << now->l[i]->val << endl;
		for(int j=now->l[i]->mx; j<now->l[i]->val; j++) res.pb('P');
		print(now->l[i]);
		res.pb('-');
	}
	if(cnt==0){
		//res.pb('P');
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, t=0;
	cin >> n;
	string s;
	for(int i=0; i<n; i++){
		cin >> s;
		if(s.length()>t){
			m=s;
			t=s.length();
		}
		insert(s);
	}
	swp();
	print(root);
	while(res[res.size()-1]=='-'){
		res.pop_back();
	}
	cout << res.size() << endl;
	for(int i=0; i<res.size(); i++) if(res[i]!='#')cout << res[i] << '\n';
	return 0;
}

Compilation message

printer.cpp: In function 'void insert(std::__cxx11::string)':
printer.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s.length(); i++){
               ~^~~~~~~~~~~
printer.cpp: In function 'void swp()':
printer.cpp:43:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ind<m.length()){
        ~~~^~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:79:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(s.length()>t){
      ~~~~~~~~~~^~
printer.cpp:91:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<res.size(); i++) if(res[i]!='#')cout << res[i] << '\n';
               ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 592 KB Output is correct
2 Correct 3 ms 624 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2328 KB Output is correct
2 Correct 8 ms 2740 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6720 KB Output is correct
2 Correct 34 ms 13812 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 39860 KB Output is correct
2 Correct 158 ms 90376 KB Output is correct
3 Correct 83 ms 90376 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 90376 KB Output is correct
2 Correct 189 ms 108448 KB Output is correct
3 Correct 106 ms 108448 KB Output is correct
4 Correct 198 ms 108448 KB Output is correct