fork download
copy 
  1. #include <bits/stdc++.h>
  2. // #include <ext/pb_ds/assoc_container.hpp>
  3. // #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. // using namespace __gnu_pbds;
  7.  
  8. // #pragma GCCoptimize("O3")
  9. // #pragma GCCtarget("sse4")
  10. // #pragma GCCoptimize("unroll-loops")
  11.  
  12. #define vi vector<int>
  13. #define PB push_back
  14. #define vll vector<long long>
  15. #define ll long long
  16. #define all(x) x.begin(), x.end()
  17. #define F first
  18. #define S second
  19. #define ld long double
  20. #define vld vector<long double>
  21. #define pll pair<ll, ll>
  22. #define pii pair<int, int>
  23. #define vpii vector<pair<int, int>>
  24. #define GCD __gcd
  25.  
  26. const ll mod = 998244353;
  27. const ll MOD = 1e9 + 7;
  28. const ll INF = 1e18;
  29. const int inf = 1e9;
  30.  
  31. vector<int> sort_cyclic_shifts(string const &s){
  32.     int n = s.size();
  33.     const int alphabet = 256;
  34.     vi p(n), c(n), cnt(max(alphabet, n), 0);
  35.     for (int i = 0; i < n; i++){
  36.         cnt[s[i]]++;
  37.     }
  38.     for (int i = 1; i < alphabet; i++){
  39.         cnt[i] += cnt[i - 1];
  40.     }
  41.     for (int i = 0; i < n; i++){
  42.         p[--cnt[s[i]]] = i;
  43.     }
  44.     c[p[0]] = 0;
  45.     int classes = 1;
  46.     for (int i = 1; i < n; i++){
  47.         if (s[p[i]] != s[p[i - 1]]){
  48.             classes++;
  49.         }
  50.         c[p[i]] = classes - 1;
  51.     }
  52.     vi pn(n), cn(n);
  53.     for (int h = 0; (1 << h) < n; h++){
  54.         for (int i = 0; i < n; i++) {
  55.             pn[i] = p[i] - (1 << h);
  56.             if (pn[i] < 0) pn[i] += n;
  57.         }
  58.         fill(cnt.begin(), cnt.end(), 0);
  59.         for (int i = 0; i < n; i++){
  60.             cnt[c[pn[i]]]++;
  61.         }
  62.         for (int i = 1; i < classes; i++){
  63.             cnt[i] += cnt[i - 1];
  64.         }
  65.         for (int i = n - 1; i >= 0; i--){
  66.             p[--cnt[c[pn[i]]]] = pn[i];
  67.         }
  68.         cn[p[0]] = 0;
  69.         classes = 1;
  70.         for (int i = 1; i < n; i++){
  71.             pii cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
  72.             pii prev = {c[p[i - 1]], c[(p[i - 1] + (1 << h)) % n]};
  73.             if (cur != prev){
  74.                 classes++;
  75.             }
  76.             cn[p[i]] = classes - 1;
  77.         }
  78.         c.swap(cn);
  79.     }
  80.     return p;
  81. }
  82.  
  83. vector<int> suffix_array(string s){
  84.     s += '$';
  85.     vi ret = sort_cyclic_shifts(s);
  86.     ret = vi(ret.begin() + 1, ret.end());
  87.     return ret;
  88. }
  89.  
  90. void solve(int tst){
  91.  
  92.     int n;
  93.     cin >> n;
  94.     vector<char> a(n);
  95.     for (int i = 0; i < n; i++){
  96.         cin >> a[i];
  97.         a.PB(a[i]);
  98.     }
  99.     string s;
  100.     for (auto elem: a){
  101.         s += elem;
  102.     }
  103.  
  104.     vi p = suffix_array(s);
  105.     vector<int> ans(n);
  106.     int L = 0, R = 2 * n - 1;
  107.  
  108.     for (int i = 0; i < n; i++){
  109.         char search = ('0') + ('1' - s[i]);
  110.         int l = L - 1, r = R;
  111.         int left, right;
  112.         // cout << L << " " << R << "\n";
  113.         while (l < r - 1){
  114.             int mid = l + (r - l) / 2;
  115.             if (p[mid] + i >= 2 * n) {
  116.                 l = mid;
  117.                 continue;
  118.             }
  119.             if (s[p[mid] + i] < search) l = mid;
  120.             else r = mid;
  121.         }
  122.         left = r;
  123.         if (p[r] + i >= 2 * n || s[p[r] + i] != search){
  124.             ans[i] = 0;
  125.             continue;
  126.         }
  127.         l = L, r = R + 1;
  128.         while (l < r - 1){
  129.             int mid = l + (r - l) / 2;
  130.             if (p[mid] + i == 2 * n) {
  131.                 l = mid;
  132.                 continue;
  133.             }
  134.             if (s[p[mid] + i] <= search) l = mid;
  135.             else r = mid;
  136.         }
  137.         right = l;
  138.         ans[i] = 1;
  139.         L = left;
  140.         R = right;
  141.     }
  142.     for (int i = 0; i < n; i++) cout << ans[i] << " ";
  143.     cout << "\n";
  144. }
  145.  
  146. int main(){
  147.     ios_base::sync_with_stdio(0);
  148.     cin.tie(0);
  149.     // pre();
  150.     int tc = 1;
  151.     cin >> tc;
  152.     for (int i = 1; i <= tc; i++){
  153.         solve(i);
  154.     }
  155.     return 0;
  156. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/8VgnL7
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ 4.3.2 (gcc-4.3.2)

					

					

						
created:
								
						
4 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!