Submission #951839

#	Time	Username	Problem	Language	Result	Execution time	Memory
951839		vjudge1	Type Printer (IOI08_printer)	C++17	100 / 100	110 ms	106584 KiB

printer

#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>

#define  DBG(x         ) cerr<<#x<<" = "<<(x)<<endl
#define DBG2(x, y      ) cerr<<#x<<" = "<<(x)<<", "<<#y<<" = "<<(y)<<endl
#define DBG3(x, y, z   ) cerr<<#x<<" = "<<(x)<<", "<<#y<<" = "<<(y)<<", "<<#z<<" = "<<(z)<<endl
#define DBG4(x, y, z, w) cerr<<#x<<" = "<<(x)<<", "<<#y<<" = "<<(y)<<", "<<#z<<" = "<<(z)<<", "<<#w<<" = "<<(w)<<endl
#define RAYA cerr<<" =============== "<<endl

#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fort(i, n) for(int i = 0; i <= int(n); i++)
#define fori(i, a, n) for(int i = a; i < int(n); i++)
#define forit(i, a, n) for(int i = a; i <= int(n); i++)

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

using namespace std;

template<typename T>
ostream & operator<<(ostream &os, const vector<T> &v){
    os<<"[";
    forn(i, (int) v.size()){
        if(i) os<<", ";
        os<<v[i];
    }
    os<<"]";
    return os;
}

template<typename S, typename T>
ostream & operator<<(ostream &os, const pair<S, T> &p){
	os<<"("<<p.first<<", "<<p.second<<")";
	return os;
}

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int ALP = 26;

typedef struct Node *pnode;

struct Node{
	bool v = 0;
	pair<int, int> longest = {0, -1};
	pnode m[ALP];
	Node(){
		forn(i, ALP) m[i] = NULL;
	}
};

vector<char> res;

struct Trie{
	pnode root;
	Trie(){
		root = new Node();
	}
	void insert(const string &s){
		int n = s.size();
		pnode curr = root;
		for(int i = 0; i < n; i++){
			int idx = s[i] - 'a';
			curr->longest = max(curr->longest, {n-i, idx});
			if(!curr->m[idx]) curr->m[idx] = new Node();
			curr = curr->m[idx];
		}
		curr->v = 1;
	}
	void dfs(pnode curr, bool l){
		if(curr->v) res.push_back('P');
		forn(i, ALP){
			if(!curr->m[i]) continue;
			if(curr->longest.second==i && l) continue;
			res.push_back(char(i+'a'));
			dfs(curr->m[i], 0);
			res.push_back('-');
		}
		if(curr->longest.first && l){
			res.push_back(char(curr->longest.second+'a'));
			dfs(curr->m[curr->longest.second], 1);
		}
	}
	void dfs(){
		dfs(root, 1);
	}
};

void solve(){
	
	int n;
	cin>>n;
	
	Trie printer;
	while(n--){
		string s;
		cin>>s;
		printer.insert(s);
	}
	
	printer.dfs();
	
	cout<<res.size()<<"\n";
	for(char c : res) cout<<c<<"\n";

}

int main(){

	cin.tie(NULL);
	ios::sync_with_stdio(0);

    #ifdef LOCAL
        freopen("input.in", "r", stdin);
    #else
        //~ freopen("input.in", "r", stdin);
        //~ freopen("output.out", "w", stdout);
    #endif

    //~ int tcs;
    //~ cin>>tcs;
    //~ while(tcs--){
        solve();
    //~ }

    return 0;
}

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