Submission #1303176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303176		ghammazhassan	Type Printer (IOI08_printer)	C++20	100 / 100	86 ms	51540 KiB

printer

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
// #define int long long
#define endl "\n"
#define fi first
#define se second
const int M=998244353;
// const int inf = 1e14;
const int LOG=18;
const int N=20e5+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;
int tr[N][26];
int cn[N];
int v=1;
void add(string s){
    int cur=0;
    int n=s.size();
    for (int i=0;i<n;i++){
        if (!tr[cur][s[i]-'a']){
            tr[cur][s[i]-'a']=v++;
        }
        cur=tr[cur][s[i]-'a'];
        if (i==n-1){
            cn[cur]++;
        }
    }
}
int co=0;
vector<int>ln;
vector<char>an;
string pr;
int in=-1;
int ac[25];
void rem(int s,int cur){
    in++;
    an.push_back('-');
    co++;
    if (in<pr.size() and ac[in]==0){
        ac[in]=tr[cur][pr[in]-'a'];
        rem(pr[in]-'a',tr[cur][pr[in]-'a']);
    }
    for (int i=0;i<26;i++){
        if (!tr[cur][i] or (in<pr.size() and tr[cur][i]==ac[in]))continue;
        // cout << tr[cur][i] << " ";
        rem(i,tr[cur][i]);
    }
    co++;
    if (cn[cur]){
        co++;
        an.push_back('P');
    }
    an.push_back((char)(s+'a'));
    in--;
}
void solve(){
    cin >> n;
    vector<pair<int,string>>a(n);
    for (int i=0;i<n;i++){
        cin >> a[i].se;
        a[i].fi=(a[i].se).size();
    }
    sort(a.begin(),a.end());
    for (int i=0;i<n;i++){
        add(a[i].se);
    }
    pr=a[n-1].se;
    rem(0,0);
    an.pop_back();
    reverse(an.begin(),an.end());
    int k=co-a[n-1].fi-2;
    cout << k << endl;
    for (int i=0;i<k;i++){
        cout << an[i] << endl;  
    }
}
signed main()    
{   

    // ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    // cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed << setprecision(9);
    srand(time(0));
    // int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
        solve();
        q++;
    }
}

• 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