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 las=lower_bound(indi[s[l]].begin(),indi[s[l]].end(),l)-indi[s[l]].begin()   ;
  52.     int elas=indi[s[l]][las];
  53.     for(int r=las+1;r<indi[s[l]].size();r++){
  54.         if(1){
  55.             flag=true;
  56.         ret=max(ret,rec(indi[s[l]][r]+1)+1);
  57.         }
  58.     }
  59.     if(!flag)
  60.     {
  61.         return  -1e8;
  62.     }
  63.     else{
  64.         return ret;
  65.     }
  66. }
  67.  
  68. vi ans(N);
  69. void build(int l,int i)
  70. {
  71.     if(l==n){
  72.         return ;
  73.     }
  74.     int ret=0;
  75.     bool flag=false;
  76.     int cho;
  77.     int las;
  78.     las=lower_bound(indi[s[l]].begin(),indi[s[l]].end(),l)-indi[s[l]].begin()   ;
  79.     int elas=indi[s[l]][las];
  80.     for(int r=las+1;r<indi[s[l]].size();r++){
  81.         if(1){
  82.             flag=true;
  83.             ret=max(ret,rec(indi[s[l]][r]+1)+1);
  84.             if (ret==rec(indi[s[l]][r]+1)+1){
  85.                 cho=indi[s[l]][r];
  86.             }
  87.         }
  88.  
  89.     }
  90.     ans[i]=cho-l+1;
  91.     build(cho+1,i+1);
  92.  
  93. }
  94.  
  95. void solve(){
  96.     cin>>n;
  97.     cin>>s;
  98.     for (int i=0;i<n;i++){
  99.         indi[s[i]].push_back(i);
  100.     }
  101.     int ans1=rec(0);
  102.     if (ans1<=0)
  103.     {
  104.         cout<<-1<<dl;
  105.     }
  106.     else
  107.     {
  108.     build(0,0);
  109.         cout<<ans1<<dl;
  110.         for(int i=0;i<ans1;i++)
  111.         {
  112.             cout<<ans[i]<<" ";
  113.         }
  114.         cout<<dl;
  115.     }
  116. }
  117. int32_t main(){
  118.     Antoine_Sobhy();
  119.     int t=1;
  120.     // cin>>t;
  121.     memset(dp,-1,sizeof(dp));
  122.     while(t--) {
  123.         solve();
  124.     }
  125.  
  126.     return 0;
  127.  
  128. }
Success #stdin #stdout 0.01s 9400KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/lD4WIn
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!