fork download
copy 
  1. // ROOT : DRAGON3012009 : WA in Real Life
  2. #include <bits/stdc++.h>
  3. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  4. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  5. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  6. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  7. #define ll short
  8. #define el "\n"
  9. #define fi first
  10. #define se second
  11. #pragma GCC optimize("Ofast")
  12. #pragma GCC target("avx2")
  13. #pragma GCC optimize("O3")
  14. #pragma GCC optimize("unroll-loops")
  15. #define _ROOT_ int main()
  16. #define M 1000000007
  17. #define MAXN 505
  18. #define Bit(i) (1LL << i )
  19. #define INF (1ll<<30)
  20. #define NAME "file"
  21. #define debug(a) cout << #a << " = " << a << endl;
  22. using namespace std;
  23.  
  24.  
  25. ll n, m , q , tmp  ;
  26. string ans ;
  27. string a[MAXN] ;
  28. string cp[MAXN ] ;
  29.  
  30. ll lenlienquan(string x, string y) {
  31.     ll len1 = x.size();
  32.     ll len2 = y.size();
  33.  
  34.     for(ll len = min(len1, len2); len > 0; len--) {
  35.         if(x.substr(len1 - len) == y.substr(0, len)) {
  36.             return len;
  37.         }
  38.     }
  39.     return 0;
  40. }
  41.  
  42. void init() {
  43.     cin >> n ;
  44.     FOR(i , 1 , n ) cin >> a[i] ;
  45.     tmp = n ; 
  46. }
  47.  
  48. void solve() {
  49.     n = tmp ;
  50.     random_shuffle(a + 1 , a + n + 1 ) ;
  51.     FOR(i , 1 , n ) cp[i] = a[i] ;
  52.     vector<string> valid;
  53.     FOR(i, 1, n) {
  54.         bool sub = false;
  55.         FOR(j, 1, n) {
  56.             if(i == j) continue;
  57.             if(cp[j].find(cp[i]) != string::npos) {
  58.                 if (cp[j].size() > cp[i].size() || (cp[j].size() == cp[i].size() && i > j)) {
  59.                     sub = true;
  60.                     break;
  61.                 }
  62.             }
  63.         }
  64.         if(!sub) valid.push_back(cp[i]);
  65.     }
  66.  
  67.     n = valid.size();
  68.  
  69.     FOR(i, 1, n) cp[i] = valid[i - 1];
  70.  
  71.     vector<bool> dead(n + 1, false);
  72.     ll rem = n;
  73.  
  74.     while(rem > 1) {
  75.         ll max_ol = -1;
  76.         ll best_u = -1, best_v = -1;
  77.  
  78.         FOR(i, 1, n) {
  79.             if(dead[i]) continue;
  80.             FOR(j, 1, n) {
  81.                 if(dead[j] || i == j) continue;
  82.  
  83.                 ll tmp = lenlienquan(cp[i], cp[j]);
  84.                 if(tmp >= max_ol) {
  85.                     if(tmp == max_ol ) { 
  86.                      if(rand() % 2 == 0 ) continue ;    
  87.                     }
  88.                     max_ol = tmp;
  89.                     best_u = i;
  90.                     best_v = j;
  91.                 }
  92.             }
  93.         }
  94.  
  95.         cp[best_u] = cp[best_u] + cp[best_v].substr(max_ol);
  96.         dead[best_v] = true;
  97.         rem--;
  98.         FOR(i, 1, n) {
  99.             if(dead[i] || i == best_u) continue;
  100.             if(cp[best_u].find(cp[i]) != string::npos) {
  101.                 dead[i] = true;
  102.                 rem--;
  103.             }
  104.         }
  105.     }
  106.     string res ;
  107.     FOR(i, 1, n) {
  108.         if(!dead[i]) {
  109.             res = cp[i] ;
  110.             break;
  111.         }
  112.     }
  113.  
  114.     ll len_res = res.size();
  115.     for(ll len = len_res - 1; len > 0; len--) {
  116.         if(res.substr(len_res - len) == res.substr(0, len)) {
  117.             res = res.substr(0, len_res - len);
  118.             break;
  119.         }
  120.     }
  121.     if(ans.empty() ) ans = res ;
  122.     else if(res.size() < ans.size() ) {
  123.         ans = res ;
  124.     }
  125. }
  126.  
  127. _ROOT_ {
  128.     // freopen(NAME".inp" , "r" , stdin);
  129.     // freopen(NAME".out" , "w", stdout) ;
  130.     srand(time(nullptr));
  131.     ios_base::sync_with_stdio(0);
  132.     cin.tie(0);
  133.     cout.tie(0);
  134.     int t = 1; // cin >> t ;
  135.     while(t--) {
  136.         init();
  137.         ll magic  ;
  138.         if(n <= 200 ) magic = 100 ; 
  139.         else magic = 2 ; 
  140.         while(magic -- ) solve();
  141.         cout << ans << el ;
  142.     }
  143.     return (0&0);
  144. }
  145.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/VYlcT3
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
6 hours 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!