Submission #1206551

#TimeUsernameProblemLanguageResultExecution timeMemory
1206551leandropinaType Printer (IOI08_printer)C++20
100 / 100
103 ms62040 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define NMAX 100005 #define int long long #define pii pair<int,int> #define tt tuple<int,int,int> #define INF 1e18 #define MOD 1000000007 #define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ost tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> #define LSB(x) ((x)&-(x)) #define count_bits(x) __builtin_popcount(x) #define leading_zeros(x) __builtin_clz(x) #define trailing_zeros(x) __builtin_ctz(x) #define all(x) begin(x),end(x) #define pb push_back #define eps 1e-9 struct node{ int id; int cnt; map<char,int>next; node(){ id = -1; cnt = 0; next.clear(); } }; vector<node>tri={node()}; int new_node(){ tri.pb(node()); return tri.size()-1; } void insere(string &s, int i){ int x = 0; tri[x].cnt++; for(auto ch:s){ if(tri[x].next.count(ch)==0){ tri[x].next[ch] = new_node(); } x = tri[x].next[ch]; tri[x].cnt++; } tri[x].id = i; } int qtdd(string a, string b){ int n = a.size(); int m = b.size(); int qtd = 0; for(int i=0;i<min(n,m);i++){ if(a[i]==b[i]) qtd++; else break; } return qtd; } string ans =""; void solve(int x){ if(tri[x].id!=-1){ ans.pb('P'); } vector< pair<int,char> >v; for(auto [ch,next_id]:tri[x].next){ v.pb({next_id,ch}); } sort(all(v)); for(auto [next_id,ch]:v){ ans.pb(ch); solve(next_id); ans.pb('-'); } } int32_t main(){ faster int n; cin >> n; vector<string>v; vector< pair<int,string> >vv; int mx = 0; string s_mx; for(int i=0;i<n;i++){ string s; cin >> s; if( s.size() > mx ){ mx = s.size(); s_mx = s; } v.pb(s); } for(int i=0;i<n;i++){ int qtdcomum = qtdd(s_mx,v[i]); vv.pb({qtdcomum,v[i]}); } sort(all(vv)); for(int i=0;i<n;i++){ insere(vv[i].second,i); } solve(0); while(ans.back()=='-') ans.pop_back(); cout << ans.size() << '\n'; for(auto it:ans) cout << it << '\n'; } /* int dp[estados]; //dp[i] é 1 se é um estado vencedor pro player1 int solve(int x){ if(dp[x]!=-1) return dp[x]; int turno = tri[x].nivel & 1; dp[x] = 0; if(tri[x].cnt[turno]==0) return 0; for(auto [ch,next_id]:tri[x].next){ if(solve(next_id)==0){ dp[x] = 1; } } return dp[x]; } */
#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...