Submission #385455

#	Time	Username	Problem	Language	Result	Execution time	Memory
385455		negar_a	Type Printer (IOI08_printer)	C++14	20 / 100	89 ms	35716 KiB

printer

//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 25e3 * 20 + 5;
int mat[maxn][26], h[maxn], mh[maxn];
vector <pair <int, char>> adj[maxn];
vector <char> ans;

int cnt = 1;
void add(string s, int v, int h){
	if(h == s.size()){
		return;
	}
	if(!mat[v][s[h] - 'a']){
		mat[v][s[h] - 'a'] = cnt;
		adj[v].pb({cnt, s[h]});
		cnt ++;
	}
	add(s, mat[v][s[h] - 'a'], h + 1);
}

bool cmp(pair <int, char> a, pair <int, char> b){
	return mh[a.F] < mh[b.F];
}

void dfs(int v){
	sort(adj[v].begin(), adj[v].end(), cmp);
	if(!adj[v].size()){
		ans.pb('P');
	}
	for(auto p : adj[v]){
		int u = p.F;
		ans.pb(p.S);
		dfs(u); 
	}
	ans.pb('-');
}
void dfs1(int v){
	mh[v] = h[v];
	for(auto p : adj[v]){
		int u = p.F;
		h[u] = h[v] + 1;
		dfs1(u); 
		mh[v] = max(mh[v], mh[u]);
	}
}

int main(){
	fast_io;
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++){
		string s;
		cin >> s;
		add(s, 0, 0);
	}
	dfs1(0);
	dfs(0);
	while(ans.back() == '-'){
		ans.pop_back();
	}
	cout << ans.size() << '\n';
	for(char u : ans){
		cout << u << '\n';
	}
	return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void add(std::string, int, int)':
printer.cpp:21:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  if(h == s.size()){
      |     ~~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10