Submission #685227

#TimeUsernameProblemLanguageResultExecution timeMemory
685227JANCARAPANType Printer (IOI08_printer)C++17
100 / 100
121 ms76264 KiB
#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? */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...