Submission #467748

#	Time	Username	Problem	Language	Result	Execution time	Memory
467748		MohamedFaresNebili	Type Printer (IOI08_printer)	C++14	20 / 100	70 ms	39088 KiB

printer

#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using ld  = long double;
using db  = double;
using ii  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vii = vector<ii>;
using vpl = vector<pl>;

#define mp make_pair
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()

const int MOD = 1000*1000*1000+7;
const long double EPS = 0.000000001;
const long long INF = 1e18;

struct node{
    node* children[26]; bool visited=false; node* parent=nullptr; bool marked=false;
    node() {
        for(int l=0;l<26;l++) children[l]=nullptr;
    }
};
node* root; int n; string len="";
vector<char>ans;
void add(string s)
{
    node* next=root;
    for(auto u:s) {
        int i=u-'a';
        if(next->children[i]==nullptr) next->children[i]=new node();
        (next->children[i])->parent=next; next=next->children[i];
    }
    if((int)s.length()>(int)len.length()) {
        next=root;
        for(auto u:len) {
            int i=u-'a';
            (next->children[i])->marked=false;
            next=next->children[i];
        }
        next=root; len=s;
        for(auto u:len) {
            int i=u-'a';
            (next->children[i])->marked=true;
            next=next->children[i];
        }
    }
}
void solve(node* r, int cnt)
{
    node* next=r; bool found=false, used=false;
    for(int l=0;l<26;l++) {
        if(next->children[l]==nullptr) continue;
        found=true;
        if((next->children[l])->visited) continue;
        used=true;
        if((next->children[l])->marked) continue;
        (next->children[l])->visited=true;
        ans.pb(char(l+'a')); solve(next->children[l], cnt); return;
    }
    if(!found) {
        ans.pb('P');
        if(cnt+1==n) return;
        
		if(next->parent!=nullptr) { ans.pb('-'); solve(next->parent, cnt+1); }
    }
    else if(used) {
        for(int l=0;l<26;l++) {
            if(next->children[l]==nullptr) continue;
            if((next->children[l])->visited) continue;
            (next->children[l])->visited=true;
            ans.pb(char(l+'a')); solve(next->children[l], cnt); return;
        }
    }
    else {
		
		if(next->parent!=nullptr) { ans.pb('-'); solve(next->parent, cnt); }
	}
}

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    /// freopen("closing.in", "r", stdin);
	/// freopen("closing.out", "w", stdout);
	cin>>n; root=new node();
	for(int l=0;l<n;l++) {
        string s; cin>>s; add(s);
	}
	solve(root, 0);
	cout<<(int)ans.size()<<'\n';
	for(auto u:ans) cout<<u<<'\n';
    return 0;
}

• 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