제출 #540684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540684		csamoila	Type Printer (IOI08_printer)	C++14	100 / 100	164 ms	99640 KiB

printer

#include <bits/stdc++.h>

using namespace std;

ifstream fin("input.in");
ofstream fout("input.out");

int N;
string V[101];

struct TrieNode{
    int nrcuv,nrfii;
    TrieNode *fii[26];
    TrieNode(){
        nrcuv=nrfii=0;
        for(int i=0;i<26;i++)
            fii[i]=0;
    }
};

TrieNode *root = new TrieNode;

void inserare(TrieNode *nod,char *s){
    if(*s==0){
        nod->nrcuv++;
        return;
    }
    if(nod->fii[*s-'a']==0){
        nod->nrfii++;
        nod->fii[*s-'a'] = new TrieNode;
    }

    inserare(nod->fii[*s-'a'],s+1);
}

char cuvmax[21];

int rez;
int cont;

string S;

void f(TrieNode *nod,string s,char *cuv,int ok){
    int p=-1;
    for(int i=0;i<26;i++){
        if(nod->fii[i]==0) continue;
        if((char)(i+'a')==*cuv and ok==1){
            p=i;
            continue;
        }
        S+=(char)(i+'a');
        if(nod->fii[i]->nrcuv!=0)
            S+='P',nod->fii[i]->nrcuv=0,cont++;
        f(nod->fii[i],s+(char)(i+'a'),cuv+1,0);
        if(cont<N) S+='-';
    }
    if(p!=-1){
    if(nod->fii[p]==0) return;
    S+=(char)(p+'a');
    if(nod->fii[p]->nrcuv!=0)
        S+='P',cont++;
    f(nod->fii[p],s+(char)(p+'a'),cuv+1,1);
    if(cont<N) S+='-';
    }
}

int main()
{
    cin >> N;
    for(int i=1;i<=N;i++){
        char s[21];
        cin >> s;
        inserare(root,s);
        if(strlen(s)>strlen(cuvmax))
            strcpy(cuvmax,s);
    }
    f(root,"",cuvmax,1);
    cout << S.size() << '\n';
    for(auto it:S) cout << it << '\n';
    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