Submission #371321

#TimeUsernameProblemLanguageResultExecution timeMemory
371321uacoder123Type Printer (IOI08_printer)C++14
100 / 100
163 ms37356 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define F first #define S second #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i) #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i) #define all(x) (x).begin(), (x).end() #define sz(x) lli(x.size()) #define mp(i,a) make_pair(i,a) #define pb(a) push_back(a) #define bit(x,b) (x&(1LL<<b)) typedef long long int lli; typedef pair <lli,lli> ii; typedef pair <ii,lli> iii; typedef vector <lli> vi; typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; vi al[25000*26]; int dp[25000*26],dp1[25000*26],id[25000*26],n,c=1,co[25000*26]; string s; void ad(int node,int cur) { if(cur==s.size()) { co[node]++; return; } for(int i=0;i<al[node].size();++i) { if(id[al[node][i]]==s[cur]-'a') return ad(al[node][i],cur+1); } al[node].pb(c); id[c]=s[cur]-'a'; c++; return ad(c-1,cur+1); } void dfs(int node) { for(int i=0;i<al[node].size();++i) dfs(al[node][i]); int m=0; dp[node]=2+co[node]; dp1[node]=1+co[node]; for(int i=0;i<al[node].size();++i) { dp[node]+=dp[al[node][i]]; dp1[node]+=dp[al[node][i]]; m=min(m,-dp[al[node][i]]+dp1[al[node][i]]); } dp1[node]+=m; } int x=0; void dfs1(int node,int t) { if(node!=0) { x++; if(x>dp1[0]-1) exit(2); cout<<char(id[node]+'a')<<'\n'; } while(co[node]) { x++; if(x>dp1[0]-1) exit(3); cout<<'P'<<'\n'; co[node]--; } ii m=mp(100,-1); if(t==1) { for(int i=0;i<al[node].size();++i) m=min(m,mp(0ll-dp[al[node][i]]+dp1[al[node][i]],i*1LL)); } for(int i=0;i<al[node].size();++i) { if(i!=m.S) dfs1(al[node][i],0); } if(m.S!=-1) dfs1(al[node][m.S],1); if(t==0) { x++; if(x>dp1[0]-1) exit(4); cout<<'-'<<'\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n; for(int i=0;i<n;++i) { cin>>s; ad(0,0); } dfs(0); cout<<dp1[0]-1<<'\n'; dfs1(0,1); return 0; }

Compilation message (stderr)

printer.cpp: In function 'void ad(int, int)':
printer.cpp:24:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   if(cur==s.size())
      |      ~~~^~~~~~~~~~
printer.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int i=0;i<al[node].size();++i)
      |               ~^~~~~~~~~~~~~~~~
printer.cpp: In function 'void dfs(int)':
printer.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int i=0;i<al[node].size();++i)
      |               ~^~~~~~~~~~~~~~~~
printer.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int i=0;i<al[node].size();++i)
      |               ~^~~~~~~~~~~~~~~~
printer.cpp: In function 'void dfs1(int, int)':
printer.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<al[node].size();++i)
      |                 ~^~~~~~~~~~~~~~~~
printer.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int i=0;i<al[node].size();++i)
      |               ~^~~~~~~~~~~~~~~~
#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...