fork download
copy 
  1.  #include <limits>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define int   long long
  5. #define dl '\n'
  6. const int INF = 1e18;
  7. #define printvec(v) for(int i=0;i<v.size();i++){cout<<v[i]<<" ";}cout<<endl;
  8. #define loop(i,n){} for(int i=0;i<n;i++){}
  9. #define read(v,n)   for(int i=0;i<n;i++){cin>>v[i];}
  10. #define all(v)                ((v).begin()), ((v).end())
  11. #define rall(v)                ((v).rbegin()), ((v).rend())
  12. typedef vector<int> vi;
  13. typedef vector<pair<int,int>> vip;
  14. #define ll long long
  15. void Antoine_Sobhy(){
  16.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  17. #ifndef ONLINE_JUDGE
  18.     // freopen("business.in", "r", stdin);
  19.     freopen("/home/antoine/Desktop/acpc/input.txt", "r", stdin);
  20.     freopen("/home/antoine/Desktop/acpc/output.txt", "w", stdout);
  21. #endif
  22. }
  23.  
  24. void Read_Write() {
  25.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  26.     freopen("nocross.in", "r", stdin);
  27.     freopen("nocross.out", "w", stdout);
  28. }
  29. int ce;
  30. vi coins={1,5,10,25,50};
  31. int query(int i,int j) {
  32.     cout<<"?"<<" "<<i<<" "<<j<<dl;
  33.     cout.flush();
  34.     int x;
  35.     cin>>x;
  36.     return x;
  37. }
  38. const int N=4e5+2;
  39. int dp[N];
  40. map<char,vi>indi;
  41. int n;
  42. string s;
  43. int rec(int l){
  44.     if(l==n){
  45.         return 0;
  46.     }
  47.     int &ret=dp[l];
  48.     if (~ret) return ret;
  49.     ret=-1e8;
  50.     bool flag=false;
  51.     int counter=0;
  52.  
  53.    int las=lower_bound(indi[s[l]].begin(),indi[s[l]].end(),l)-indi[s[l]].begin()   ;
  54.     for(int r=las+1;r<indi[s[l]].size();r++){
  55.         if(counter<10){
  56.             counter++;
  57.             flag=true;
  58.         ret=max(ret,rec(indi[s[l]][r]+1)+1);
  59.         }
  60.         else
  61.         {
  62.             break;
  63.         }
  64.     }
  65.     if(!flag)
  66.     {
  67.         return  -1e8;
  68.     }
  69.     else{
  70.         return ret;
  71.     }
  72. }
  73.  
  74. vi ans(N);
  75. void build(int l,int i)
  76. {
  77.     if(l==n){
  78.         return ;
  79.     }
  80.     int ret=0;
  81.     bool flag=false;
  82.     int cho;
  83.     int las;
  84.     las=lower_bound(indi[s[l]].begin(),indi[s[l]].end(),l)-indi[s[l]].begin()   ;
  85.     int elas=indi[s[l]][las];
  86.     int counter=0;
  87.     for(int r=las+1;r<indi[s[l]].size();r++){
  88.         if(counter<=10){
  89.             counter++;
  90.             flag=true;
  91.             ret=max(ret,rec(indi[s[l]][r]+1)+1);
  92.             if (ret==rec(indi[s[l]][r]+1)+1){
  93.                 cho=indi[s[l]][r];
  94.             }
  95.         }
  96.     }
  97.     ans[i]=cho-l+1;
  98.     build(cho+1,i+1);
  99.  
  100. }
  101.  
  102. void solve(){
  103.     cin>>n;
  104.     cin>>s;
  105.     for (int i=0;i<n;i++){
  106.         indi[s[i]].push_back(i);
  107.     }
  108.     int ans1=rec(0);
  109.     if (ans1<=0)
  110.     {
  111.         cout<<-1<<dl;
  112.     }
  113.     else
  114.     {
  115.     build(0,0);
  116.         cout<<ans1<<dl;
  117.         for(int i=0;i<ans1;i++)
  118.         {
  119.             cout<<ans[i]<<" ";
  120.         }
  121.         cout<<dl;
  122.     }
  123. }
  124. int32_t main(){
  125.     Antoine_Sobhy();
  126.     int t=1;
  127.     // cin>>t;
  128.     memset(dp,-1,sizeof(dp));
  129.     while(t--) {
  130.         solve();
  131.     }
  132.  
  133.     return 0;
  134.  
  135. }
Success #stdin #stdout 0.01s 9292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/BqOwio
language:
C++14 (gcc 8.3)
created:
7 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!