Submission #1194104

#TimeUsernameProblemLanguageResultExecution timeMemory
1194104Hamed_GhaffariType Printer (IOI08_printer)C++20
100 / 100
32 ms7172 KiB
#include <bits/stdc++.h> using namespace std; const int MXN = 25002; int n, lcp[MXN]; string s[MXN], S[MXN]; void srt(vector<int> &vec, int j) { if(vec.size()<=1) return; vector<int> emp; vector<vector<int>> sep(26); for(int i : vec) if(s[i].size()<=j) emp.push_back(i); else sep[s[i][j]-'a'].push_back(i); vector<int> ord; for(int i=0; i<26; i++) if(!sep[i].empty()) { srt(sep[i], j+1); ord.push_back(i); } sort(ord.begin(), ord.end(), [&](int x, int y) { return s[sep[x].back()].size() < s[sep[y].back()].size(); }); vec.clear(); for(int i : emp) vec.push_back(i); for(int i : ord) for(int x : sep[i]) vec.push_back(x); } int32_t main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); cin >> n; for(int i=0; i<n; i++) cin >> s[i]; vector<int> ord(n); iota(ord.begin(), ord.end(), 0); srt(ord, 0); for(int i=0; i<n; i++) S[i] = s[ord[i]]; for(int i=0; i+1<n; i++) { lcp[i] = 0; while(lcp[i]<S[i].size() && lcp[i]<S[i+1].size() && S[i][lcp[i]]==S[i+1][lcp[i]]) lcp[i]++; } string ans; for(int i=0; i<n; i++) { for(int j=(i==0 ? 0 : lcp[i-1]); j<S[i].size(); j++) ans.push_back(S[i][j]); ans.push_back('P'); if(i+1<n) for(int j=0; j<S[i].size()-lcp[i]; j++) ans.push_back('-'); } cout << ans.size() << '\n'; for(char c : ans) cout << c << '\n'; return 0; }
#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...