Submission #685227

#	Time	Username	Problem	Language	Result	Execution time	Memory
685227		JANCARAPAN	Type Printer (IOI08_printer)	C++17	100 / 100	121 ms	76264 KiB

printer

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

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x);
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr <<__func__<<":"<<" [" << #x << "] = ["; _print(x); /*cerr << "\e[39m" << endl;*/
#else
#define dbg(x...)
#endif


#define ll long long
#define ld long double
//#define int long long


#define fi first
#define se second
#define pb push_back
#define ii pair<ll,ll>
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(x) (int)x.size()
#define endl '\n'

const ll N = 25000, INF = 1e18, MOD = 1e9+7;
const int S = 26;

int t = 0;

struct Node {
  //vector<int> nxt;
  int nxt[S];
  bool is_word = 0;
  int height = 0;
  Node() {
    //nxt.assign(S, -1);
    for (int i = 0; i < S; i++) nxt[i] = -1;
  }
};

//vector<Node> trie(1);
Node trie[N * S];

void add_str(string& s) {
  int v = 0;
  for (int i = 0; i < sz(s); i++) {
    int cur = s[i] - 'a';
    if (trie[v].nxt[cur] == -1) {
      trie[v].nxt[cur] = ++t;
      //trie[v].nxt[cur] = sz(trie);
      //trie.emplace_back();
    }
    v = trie[v].nxt[cur];
    trie[v].height = max(trie[v].height, sz(s) - i);
    if (i == sz(s) - 1) {
      trie[v].is_word = 1;
    }
  }
}



void solve() {
  int n;
  cin >> n;
  
  vector<string> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    add_str(a[i]);
  }
  
  vector<char> ans;
  
  function<void(int)> dfs = [&] (int v) {
    if (trie[v].is_word) ans.emplace_back('P');
    
    int mx = -1, who = -1;
    for (int i = 0; i < S; i++) {
      int u = trie[v].nxt[i];
      if (u == -1) continue;
      if (mx < trie[u].height) {
        mx = trie[u].height;
        who = i;
      }
    }
    
    //dbg(char('a' + who), mx)
    
    for (int i = 0; i < S; i++) {
      int u = trie[v].nxt[i];
      if (u == -1 || i == who) continue;
      ans.emplace_back(char('a' + i));
      dfs(u);
    }
    if (who != -1) {
      ans.emplace_back(char('a' + who));
      dfs(trie[v].nxt[who]);
    }
    ans.emplace_back('-');
  };
  
  dfs(0);
  
  while (ans.back() == '-') ans.pop_back();
  
  cout << sz(ans) << endl;
  for (int i = 0; i < sz(ans); i++) {
    cout << ans[i] << endl;
  }
  
  // READ AT THE BOTTOM PLS!
}

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while (tt--) solve();
  return 0;
}

/* stuff you should look for
  * int overflow, array bounds
  * special cases (n = 1?)
  * READ CONSTRAINTS
  * reset variables?
  * STAY ORGANIZED
*/

/* 
 Suppose I did find such a solution, what would it look like? 
 What characteristics it would have? 
 Can we toy around with such a solution so that it remains optimal?
*/

• 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