oj.uz

Submission #492128

# Submission time Handle Problem Language Result Execution time Memory
492128 2021-12-05T14:53:56 Z gg123_pe Type Printer (IOI08_printer) C++17
100 / 100
 205 ms 8812 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 2 ms 1612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 3 ms 1740 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1868 KB Output is correct
2 Correct 6 ms 1868 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2252 KB Output is correct
2 Correct 39 ms 2756 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3188 KB Output is correct
2 Correct 55 ms 3756 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 4796 KB Output is correct
2 Correct 149 ms 7760 KB Output is correct
3 Correct 100 ms 7220 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 5308 KB Output is correct
2 Correct 187 ms 8800 KB Output is correct
3 Correct 117 ms 7916 KB Output is correct
4 Correct 205 ms 8812 KB Output is correct