fork download 
  1. #include<iostream>
  2. #include<vector>
  3. #include<set>
  4. #include<algorithm>
  5.  
  6. using namespace std;
  7.  
  8. vector <string> b[26],u[26];
  9. set <string> pref;
  10.  
  11. int main(int argc, char const *argv[]) {
  12.   ios_base::sync_with_stdio(0);
  13.   int n,i,val=0;
  14.   bool fin_ans=true;
  15.   char ch;
  16.   string s;
  17.   cin>>n;
  18.  
  19.   for(i=0;i<n;i++){
  20.     cin>>ch>>s;
  21.     int ind = s[0]-'a';
  22.     if(ch=='+')
  23.       u[ind].push_back(s);
  24.     else
  25.       b[ind].push_back(s);
  26.   }
  27.   std::vector< pair<int,int> > v;
  28.   for(i=0;i<26;i++){
  29.       v.push_back(make_pair(b[i].size()+u[i].size(),i));
  30.       sort(u[i].begin(),u[i].end());
  31.       sort(b[i].begin(),b[i].end());
  32.   }
  33.   sort(v.begin(),v.end());
  34.  
  35.  
  36.  
  37.   for(int in=25;in>=0;in--){
  38.  
  39.     i = v[in].second;
  40.     int size = b[i].size();
  41.     for(int j=0;j<size;j++){
  42.       string block = b[i][j];
  43.       int len_cut=1;
  44.       int comparison_index = -1;
  45.       int len1 = block.length();
  46.       int s_size = u[i].size();
  47.       bool ans = true , big =false;
  48.       for(int k=0;k<s_size;k++){
  49.         string unblock = u[i][k];
  50.         if(unblock>block){
  51.           big = true;
  52.           comparison_index = k-1;
  53.           break;
  54.         }
  55.       }
  56.       if(big == false)
  57.         comparison_index = u[i].size()-1;
  58.       if(comparison_index != -1){
  59.         string unblock = u[i][comparison_index];
  60.         int len2 = unblock.length();
  61.         int l=0;
  62.         while (l<len1&&l<len2&&block[l]==unblock[l]) {
  63.           l++;
  64.         }
  65.         if(l==len1)
  66.           ans = false;
  67.         else{
  68.           len_cut = max(len_cut,l+1);
  69.         }
  70.       }
  71.       comparison_index++;
  72.       if(u[i].size()>comparison_index){
  73.         string unblock = u[i][comparison_index];
  74.         int len2 = unblock.length();
  75.         int l=0;
  76.         while (l<len1&&l<len2&&block[l]==unblock[l]) {
  77.           l++;
  78.         }
  79.         if(l==len1)
  80.           ans = false;
  81.         else{
  82.           len_cut = max(len_cut,l+1);
  83.         }
  84.       }
  85.       fin_ans = ans;
  86.     //  cout<<"INSERTING "<<block.substr(0,len_cut)<<" BLOCK = "<<block<<" FIN_ANS = "<<fin_ans<<endl;
  87.       pref.insert(block.substr(0,len_cut));
  88.       if(fin_ans==false)
  89.         break;
  90.     }
  91.     if(fin_ans==false)
  92.       break;
  93.   }
  94.  
  95.   if(!fin_ans)
  96.     cout<<"-1\n";
  97.   else{
  98.     cout<<pref.size()<<"\n";
  99.     std::set<string>::iterator it;
  100.     for(it=pref.begin();it!=pref.end();it++)
  101.       cout<<*it<<"\n";
  102.   }
  103.  
  104.   return 0;
  105. }
  106.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
7
+ acbc
+ abbm
+ aacd
+ abcd
- aadz
- arm
- abbc
stdout 
3
aad
abbc
ar
https://ideone.com/vtw6k2
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!