oj.uz

Submission #287851

# Submission time Handle Problem Language Result Execution time Memory
287851 2020-09-01T04:45:25 Z Bill_00 Type Printer (IOI08_printer) C++14
80 / 100
 1000 ms 62012 KB 
#include <bits/stdc++.h>
#define ff first
#define ll long long
#define ss second
#define pb push_back
#define pp push
#define mp make_pair
using namespace std;
string s[25001];
unordered_map<string,vector<int> >m;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	int u[n+1]={0},id,o=0;
	for(int i=1;i<=n;i++){
		m[""].pb(i);
		cin >> s[i];
		string a="";
		for(int j=0;j<s[i].size();j++){
			a+=s[i][j];
			m[a].pb(i);
		}
		if(s[i].size()>o){
			o=s[i].size();
			id=i;
		}
	}
	vector<int>ans;
	string b=s[id];
	ans.pb(id);
	u[id]=1;
	int k=1,trans[25001];
	while(k<n){
		int flag=0;
		while(m[b].size()){
			if(u[m[b][0]]){
				m[b].erase(m[b].begin());
			}
			else{
				flag++;
				break;	
			}
		}
		if(flag){
			k++;
			trans[id]=b.size();
			//cout << trans[id] << endl;
			id=m[b][0];
			u[id]++;
			ans.pb(id);
			b=s[id];
		}
		else{
			b.erase(b.end()-1);
		} 
	}
	vector<char>res;
	for(int i=0;i<s[ans[ans.size()-1]].size();i++){
		res.pb(s[ans[ans.size()-1]][i]);
	}
	res.pb('P');
	for(int i=ans.size()-2;i>=0;i--){
		for(int j=1;j<=s[ans[i+1]].size()-trans[ans[i]];j++){
			res.pb('-');
			//cout << ans[i+1] << ' ' << s[ans[i+1]].size() << endl;
		}
		for(int j=trans[ans[i]];j<s[ans[i]].size();j++){
			res.pb(s[ans[i]][j]);
			//cout << s[ans[i]][j] << endl;
		}
		res.pb('P');
	}
	cout << res.size() << endl;
	for(int i=0;i<res.size();i++){
		cout << res[i] << endl;
	}
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int j=0;j<s[i].size();j++){
      |               ~^~~~~~~~~~~~
printer.cpp:26:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |   if(s[i].size()>o){
      |      ~~~~~~~~~~~^~
printer.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0;i<s[ans[ans.size()-1]].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int j=1;j<=s[ans[i+1]].size()-trans[ans[i]];j++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:70:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int j=trans[ans[i]];j<s[ans[i]].size();j++){
      |                           ~^~~~~~~~~~~~~~~~~
printer.cpp:77:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i=0;i<res.size();i++){
      |              ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1152 KB Output is correct
2 Correct 19 ms 1664 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2048 KB Output is correct
2 Correct 48 ms 2560 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 4620 KB Output is correct
2 Correct 287 ms 8452 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 10056 KB Output is correct
2 Correct 134 ms 4216 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 976 ms 23612 KB Output is correct
2 Execution timed out 1056 ms 53348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 18072 KB Output is correct
2 Execution timed out 1088 ms 62012 KB Time limit exceeded
3 Halted 0 ms 0 KB -