fork download
copy 
  1. //In the name of ALLAH
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <algorithm>
  6. #include <cstring>
  7. #include <cassert>
  8.  
  9. using namespace std;
  10.  
  11. #define err(x) cout<<#x<<" = "<<x<<endl;
  12. #define errdp(i,j) cout<<"dp["<<i<<"]["<<j<<"] : "<<dp[i][j]<<endl;
  13. const int N=2000+5;
  14.  
  15. short dp[2*N][2*N], sz, ans[N];
  16. char s[2*N];
  17.  
  18. int main(){
  19.   //1-based
  20.   int k;   
  21.   scanf("%d",&k);
  22.   scanf("%s",s+1);
  23.   const int n = strlen(s+1);
  24.   for (int i=1;i<=n;i++) s[i+n] = s[i];
  25.  
  26.   memset(dp,-1,sizeof dp);
  27.   for (int i=1;i<=n;i++) dp[i][i+1] = (s[i]!=s[i+1]);
  28.  
  29.   int mid;
  30.   for (int l=3;l<=n;l++){
  31.     if (l&1) continue;
  32.  
  33.     mid = l+1 >> 1;
  34.     dp[1][l] = 0;
  35.     for (int i=1;i<=mid;i++) dp[1][l] += s[i]!=s[mid+i];
  36.     dp[n+1][n+l] = dp[1][l];
  37.  
  38.     for (int i=n;i>1;i--){
  39.       mid = i+i+l-1 >> 1;
  40.       dp[i][i+l-1] = dp[i+1][i+l] - (s[mid+1]!=s[i+l]) + (s[mid+1]!=s[i]); 
  41.     }
  42.   }
  43.  
  44.   sz=-1;
  45.   for (int i=1;i<N;i++) ans[i] = 1200 /*Inf*/;
  46.  
  47.   bool chng;
  48.   for (int i=1;i<=n;i++)
  49.     for (int l=1;l<=n;l++)
  50.       if (l%2==0 && dp[i][i+l-1]<=k && sz <= l){
  51. 	sz = l;
  52. 	chng = false;
  53. 	for (int j=i;j<i+l;j++)
  54. 	  if (s[j] != ans[j-i+1]){
  55. 	    chng = s[j] < ans[j-i+1];   break;
  56. 	  }
  57.  
  58. 	if (chng)
  59. 	  for (int j=i;j<i+l;j++) ans[j-i+1] = s[j];
  60.       }
  61.  
  62.   for (int i=1;i<=sz;i++)
  63.     printf("%c",(char)ans[i]);
  64.   printf("\n");
  65.  
  66.  
  67.   return 0;
  68.  
  69. }
Success #stdin #stdout 0.02s 34760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/fUjKeG
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
9 years 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!