oj.uz

답안 #745632

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745632 2023-05-20T16:48:39 Z quochuy147 Type Printer (IOI08_printer) C++14
100 / 100
 101 ms 85828 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define file "name" 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}

const int mod = 1e9 + 7;
const int N = 1e6 + 5;

int n, check[N], d, m[N];
vector <char> res;

struct trie
{
    struct node {
        int child[26];
        int cnt, exist;
    } nodes[N];

    int cur;
    trie() : cur(0) {
        memset(nodes[0].child, -1, sizeof nodes[0].child);
        nodes[0].cnt = nodes[0].exist = 0;
    }

    int new_node() {
        cur++;
        memset(nodes[cur].child, -1, sizeof nodes[cur].child);
        nodes[cur].cnt = nodes[cur].exist = 0;
        return cur;
    }

    void insert(string s, bool check) {
        int id = 0;
        for(auto i : s) {
            int c = i - 'a';
            if(nodes[id].child[c] == -1) nodes[id].child[c] = new_node();
            id = nodes[id].child[c];
            if(check) m[id] = 1;
            nodes[id].cnt++;
        }
        nodes[id].exist++;
    }

    void dfs(int id) {
        if(d == n) {
            cout << res.size() << '\n';
            for(auto c : res) cout << c << '\n';
            exit(0);
        }
        int v_last = 0, i_last;
        for(int i = 0; i < 26; ++i) {
            int v = nodes[id].child[i];
            if(v == -1 || check[v]) continue;
            if(m[v]) {
                v_last = v;
                i_last = i;
                continue;
            }
            res.pb(i + 'a');
            for(int j = 1; j <= nodes[v].exist; ++j) {
                res.pb('P');
                d++;
            }
            check[v] = 1;
            dfs(v);
            res.pb('-');
        }
        if(v_last) {
            res.pb(i_last + 'a');
            for(int j = 1; j <= nodes[v_last].exist; ++j) {
                res.pb('P');
                d++;
            }
            check[v_last] = 1;
            dfs(v_last);
            res.pb('-');
        }
    }
};

trie T;
string s[N];
int id_mx;

void inp()
{
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> s[i];
        if(s[i].size() > s[id_mx].size()) id_mx = i; 
    }
    for(int i = 1; i <= n; ++i) {
        if(id_mx == i) T.insert(s[i], 1);
        else T.insert(s[i], 0);
    }
}

void solve()
{
    T.dfs(0);    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen(file".inp" , "r" , stdin);
    // freopen(file".out" , "w" , stdout);
    inp();
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 19 ms 31600 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 31668 KB Output is correct
2 Correct 14 ms 31572 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 15 ms 31572 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 15 ms 31660 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 31700 KB Output is correct
2 Correct 18 ms 32040 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 32476 KB Output is correct
2 Correct 17 ms 32724 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 34760 KB Output is correct
2 Correct 28 ms 38308 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 39384 KB Output is correct
2 Correct 21 ms 33492 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 51040 KB Output is correct
2 Correct 90 ms 77236 KB Output is correct
3 Correct 57 ms 55648 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 46608 KB Output is correct
2 Correct 101 ms 85828 KB Output is correct
3 Correct 63 ms 58932 KB Output is correct
4 Correct 100 ms 82884 KB Output is correct