Submission #742129

#	Time	Username	Problem	Language	Result	Execution time	Memory
742129		CSQ31	Type Printer (IOI08_printer)	C++17	100 / 100	120 ms	48648 KiB

printer

#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
int ch[26][500000];
bool pr[500000];
int ncnt = 0;
void add(int v,int i,string s){
	if(i==sz(s)){
		pr[v] = 1;
		return;
	}
	int c = s[i] - 'a';
	if(!ch[c][v])ch[c][v] = ++ncnt;
	add(ch[c][v],i+1,s);
}
string ans,lng;
int idx = 0;
void print(int v,bool deep){
	int cnt = 0;
	for(int i=0;i<26;i++){
		if(ch[i][v])cnt++;
	}
	if(!cnt){
		ans+='P';
		return;
	}
	if(pr[v]){
		ans+='P';
	}
	int c = deep?lng[idx]-'a' : -1;
	for(int i=0;i<26;i++){
		if(ch[i][v] && i != c){
			ans+=char('a'+i);
			print(ch[i][v],0);
			ans+='-';
		}
	}
	if(deep){
		ans+=char('a'+c);
		idx++;
		print(ch[c][v],1);
	}
	
}
int main()
{
	owo
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		if(sz(s) > sz(lng))lng = s;
		add(0,0,s);
	}
	print(0,1);
	cout<<sz(ans)<<'\n';
	for(auto x:ans){
		/*
		if(x=='-')cur.pop_back();
		else if(x=='P')cout<<cur<<'\n';
		else cur+=x;
		* */
		cout<<x<<'\n';
	}
}

• 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