Submission #558340

#	Time	Username	Problem	Language	Result	Execution time	Memory
558340		karon	Type Printer (IOI08_printer)	C++14	100 / 100	123 ms	101540 KiB

printer

#include <bits/stdc++.h>
#define pb push_back
#define rs resize
#define debug printf("Hello\n")
#define Pi 3.141592653589793 
#define sz(a)                 ll((a).size()) 
#define all(x)                (x).begin(), (x).end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl "\n"
#define mp make_pair
#define f first
#define s second
#define vt vector
#define rst(a,b) memset((a),(b), sizeof(a))
#define FOR(a, b, c) for (ll a = (b); (a) <  (c); ++(a))
#define FORE(a, b, c) for (ll a = (b); (a) <= (c); ++(a))
#define FORR(a, b, c) for (ll a = (b); (a) >= (c); --(a))
#define umap unordered_map
#define len(a) (a).length()
#define pqueue priority_queue
 
using namespace std;
using vi = vector<int>;    
using ui = unsigned int;                
using ll = long long;                    
using pll = pair<ll,ll>;
using vll = vector<ll>;
using ull = unsigned long long;          
using pii = pair<int, int>;

ll e(ll base, ll pwr, ll mm = LLONG_MAX){
	if(pwr == 1) return base%mm;;
	if(pwr == 0) return 1;
	if(pwr % 2 == 1){
		ull t = e(base, (pwr-1)/2,mm)%mm;

		return (t*t)%mm*base%mm ;
	}
	if(pwr % 2 == 0){
		ull t = e(base, pwr/2, mm)%mm;
		return (t*t)%mm;
	}
	return 0;
}
 
ll flt(ll a, ll p){
	return e(a,p-2,p);
}
 
ll combination(ll n, ll r){
	if(r>n/2)return combination (n,n-r);
	ll k=1;
	for(ll x=n,j=1;x>n-r||j<=r;--x,++j){
		if(x>n-r)k*=x;
		if(j<=r)k/=j;
	}
	return k;
}
 
vector<ll> getFactor(ll n){
	vector<ll> tmp;
	vector<ll> ans;
	if(n == 1)return vt<ll>{1};
	else if(n==2) return vt<ll> {1,2};
	for(ll i = 1;i<=ceil(sqrt(n));++i){
		if(!(n%i)){
			ans.pb(i);
			if(i!=n/i && abs(i-(n/i)) != 1)tmp.pb(n/i);
		}
	}
	for(ll i=tmp.size()-1;i>-1;--i){
		ans.pb(tmp[i]);
	}
	return ans;
}

bool isPrime(ll n)   {if(n == 1)return 0;for(ll i = 2;i*i <= n;++i){if(!(n%i))return 0;}return 1;}

const int dx[4] = {0,0,-1,1};
const int dy[4] = {1,-1,0,0};
const char dir[4] = {'R', 'L', 'U', 'D'};
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

struct node{
	node *arr[26] = {NULL};
	bool isend = 0;
	bool marked = 0;
};

node *root;

void insert(string &w){
	node *ptr = root;
	FOR(i,0,len(w)){
		int imap = w[i] - 'a';
		if(ptr->arr[imap] == NULL)ptr->arr[imap] = new node();
		ptr = ptr->arr[imap];
	}
	ptr->isend = 1;
}

void mark(node *n, ll depth, ll &l){
	ll cnt = 0;
	FOR(i,0,26){
		if(n->arr[i] != NULL){
			cnt++;
			mark(n->arr[i], depth + 1, l);
			n->marked |= n->arr[i]->marked;
			if(n->marked){
				return;
			}
		}
	}
	if(cnt == 0 && depth == l)n->marked = 1;
	return;
}

vt<char> ans;

void dfs(node *n, ll depth, ll &l){
	node *have = NULL;
	ll k = 0;
	if(n->isend)ans.pb('P');
	FOR(i,0,26){
		if(n->arr[i] != NULL){
			if(n->arr[i]->marked){
				have = n->arr[i];
				k = i;
				continue;
			}
			ans.pb(i+'a');
			dfs(n->arr[i], depth + 1, l);
		}
	}
	if(have != NULL){
		ans.pb(k+'a');
		dfs(have, depth + 1, l);	
	}
	ans.pb('-');
}


void solve(){
	ll n;
	cin >> n;
	vt<string> words(n);
	root = new node();
	ll maxlen = 0;
	FOR(i,0,n){
		cin >> words[i];
		maxlen = max(maxlen, (ll)len(words[i]));
		insert(words[i]);
	}
	mark(root, 0, maxlen);
	dfs(root, 0, maxlen);
	ll j = sz(ans)-1;
	while(j){
		if(ans[j]=='-')ans[j] = 0;
		else break;
		j--;
	}
	cout << j +1 << endl;
	FOR(i,0,sz(ans)){
		if(ans[i]!=0)cout << ans[i] << endl;
	}
}

int main(){
	fastio;

#ifndef ONLINE_JUDGE
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
#endif

	solve();

}

Compilation message (stderr)

printer.cpp: In function 'void insert(std::string&)':
printer.cpp:15:43: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define FOR(a, b, c) for (ll a = (b); (a) <  (c); ++(a))
      |                                       ~~~~^~~~~~
printer.cpp:96:2: note: in expansion of macro 'FOR'
   96 |  FOR(i,0,len(w)){
      |  ^~~

• 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