Submission #492128

#	Time	Username	Problem	Language	Result	Execution time	Memory
492128		gg123_pe	Type Printer (IOI08_printer)	C++17	100 / 100	205 ms	8812 KiB

printer

#include <bits/stdc++.h> 
using namespace std; 

typedef vector <int> vi; 
#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 25005;

int n, id, len; 
string s[N]; 
vector <char> v[N];
vector <string> S;

vi append(vi x, vi y){
    vi ans = x; 
    for(int a: y) ans.push_back(a);
    return ans; 
}
vi solve(vi d, int ini){
    if(ini == 20) return d; 
    vi ans, a[27]; 
    for(int x: d) if(x != id) a[v[x][ini]-'a'].push_back(x);
    for(int x: d) if(x == id) a[v[x][ini]-'a'].push_back(x);
    f(i,0,27) {
        char wi = i + 'a';
        if(a[i].size() > 0 and wi != v[id][ini]) ans = append(ans, solve(a[i], ini+1));
    }
    f(i,0,27) {
        char wi = i + 'a';
        if(a[i].size() > 0 and wi == v[id][ini]) ans = append(ans, solve(a[i], ini+1));
    }
    return ans; 
}
int cant(vector <string> v){
    int l = v.size(), ans = n + v[0].size();
    f(i,0,l-1){
        int x = v[i].size(), y = v[i+1].size(), ca = 0;
        f(j,0,min(x,y)){
            if(v[i][j] != v[i+1][j]) break;
            ca++;
        }
        ans += x + y - 2*ca;
    }
    return ans;
}
int main(){
    cin >> n;
    vi vec;  
    f(i,0,n){
        cin >> s[i]; 
        vec.push_back(i);

        int l = s[i].size();
        f(j,0,l) v[i].push_back(s[i][j]);
        f(j,l,20) v[i].push_back('{');
        if(l > len) id = i, len = l;
    }
    vi res = solve(vec, 0);

    for(int x: res) S.push_back(s[x]); 
    int ans = cant(S);

    cout << ans << endl; 
    string prev = "";
    f(i,0,n){
        int x = prev.size(), y = S[i].size(), ca = 0;
        f(j,0,min(x,y)){
            if(prev[j] != S[i][j]) break; 
            ca++;
        }
        f(j,0,x-ca) cout << "-\n";
        f(j,ca,y) cout << S[i][j] << "\n";
        cout << "P\n";
        prev = S[i];
    } 
    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