fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<long long , int>
  10. #define lll pair<long long , pair<long long , long long>>
  11. #define lii pair<long long , pair<long long , int>>
  12. #define iii pair<int , pair<int , int>>
  13. #define iiii pair<pair<int , int> , pair<int , int>>
  14. #define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
  15. #define li pair<long long , int>
  16. #define db long double
  17. #define onBit(mask , i) (mask | (1 << i))
  18. #define offBit(mask , i) (mask & (~(1 << i)))
  19.  
  20. const long long INF = 1e16;
  21. const long long MOD = 1e9 + 7;
  22. const db EPS = 1e-12;
  23. const int N = 2e5 + 7;
  24.  
  25. static int _n;
  26. static std::vector<bool> _a;
  27. static long long num_queries;
  28.  
  29. static int longest_seq_of_1s(){
  30.     int ans = 0, curr = 0;
  31.     for(int i = 0; i < _n; ++i){
  32.         if(_a[i]){
  33.             ++curr;
  34.         }
  35.         else{
  36.             curr = 0;
  37.         }
  38.         ans = std::max(ans, curr);
  39.     }
  40.     return ans;
  41. }
  42.  
  43. int flip_bits(const std::vector<bool> &flips){
  44.     assert((int)flips.size() == _n);
  45.     ++num_queries;
  46.     for(int i = 0; i < _n; ++i)
  47.         _a[i] = flips[i] ^ _a[i];
  48.     return longest_seq_of_1s();
  49. }
  50.  
  51. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  52.  
  53. int Rand(int l , int r){
  54.     return l + rd() % (r - l + 1);
  55. }
  56.  
  57. bool check(int st , int L , int cnt , int n){
  58.     vector<bool> tmp;
  59.     tmp.assign(n , 0);
  60.  
  61.     for (int i = 1 ; i <= cnt ; ++i){
  62.         tmp[st] = 1;
  63.         st += L + 1;
  64.     }
  65.  
  66.     int cur = flip_bits(tmp);
  67.     if (cur > L){
  68.         cur = flip_bits(tmp);
  69.         return 1;
  70.     }
  71.  
  72.     cur = flip_bits(tmp);
  73.     return 0;
  74. }
  75.  
  76. bool Check(int id , int L , int n){
  77.     vector<bool> tmp;
  78.     tmp.assign(n , 0);
  79.     tmp[id] = 1;
  80.  
  81.     int cur = flip_bits(tmp);
  82.  
  83.     if (cur > L){
  84.         cur = flip_bits(tmp);
  85.         return 0;
  86.     }
  87.  
  88.     cur = flip_bits(tmp);
  89.     return 1;
  90. }
  91.  
  92. pair<int , int> find_longest_subarray_of_ones(int n){
  93.     vector<bool> S;
  94.     S.assign(n , 0);
  95.     int L = flip_bits(S);
  96.     while (L > 15){
  97.         for (int i = 0 ; i < n ; ++i)
  98.             S[i] = Rand(0 , 1);
  99.  
  100.         L = flip_bits(S);
  101.     }
  102.  
  103.     if (L == 0) return {-1 , -1};
  104.     if (L == n) return {0 , n - 1};
  105.  
  106.     for (int i = 0 ; i <= L ; ++i){
  107.         if (check(i , L , n / (L + 1) , n)){
  108.             int l = 1 , r = n / (L + 1) , mid , pos = 0;
  109.             while (l <= r){
  110.                 mid = (l + r) >> 1;
  111.                 if (check(i + (l - 1) * (L + 1) , L , mid - l + 1 , n)){
  112.                     pos = mid;
  113.                     r = mid - 1;
  114.                 }
  115.                 else l = mid + 1;
  116.             }
  117.             pos = i + (pos - 1) * (L + 1);
  118.  
  119.             S.assign(n , 0);
  120.             S[pos] = 1;
  121.             int Length = flip_bits(S);
  122.  
  123.             l = pos;
  124.             while (l > 0 && Check(l - 1 , Length , n)) --l;
  125.             r = pos;
  126.             while (r < n - 1 && Check(r + 1 , Length , n)) ++r;
  127.             return {l , r};
  128.         }
  129.     }
  130. }
  131.  
  132. int main(){
  133.     freopen("difmax.inp" , "r" , stdin);
  134.     freopen("difmax.out" , "w" , stdout);
  135.     int t;
  136.     std::cin >> t;
  137.  
  138.     long long max_qs = 0;
  139.  
  140.     while(t--){
  141.         num_queries = 0;
  142.  
  143.         std::cin >> _n;
  144.         _a.resize(_n);
  145.         for(int i = 0; i < _n; ++i){
  146.             bool val;
  147.             std::cin >> val;
  148.             _a[i] = val;
  149.         }
  150.  
  151.         auto [l, r] = find_longest_subarray_of_ones(_n);
  152.         if (longest_seq_of_1s() == 0 && l == -1 && r == -1){
  153.             cout << "1 \n";
  154.             return 0;
  155.         }
  156.         if(longest_seq_of_1s() != r - l + 1){
  157.             std::cout << "0\n";
  158.             return 0;
  159.         }
  160.         if(l == 0 && r == -1){
  161.             max_qs = std::max(num_queries, max_qs);
  162.             continue;
  163.         }
  164.         if(r < l || l < 0 || l >= _n || r < 0 || r >= _n){
  165.             std::cout << "0\n";
  166.             return 0;
  167.         }
  168.  
  169.         for(int i = l; i <= r; ++i){
  170.             if(_a[i] != 1){
  171.                 std::cout << "0\n";
  172.                 return 0;
  173.             }
  174.         }
  175.  
  176.         max_qs = std::max(num_queries, max_qs);
  177.     }
  178.  
  179.     if (max_qs > 100) cout << 0 << '\n';
  180.     else std::cout << "1 " << "\n";
  181.     return 0;
  182. }
  183. //
  184. //int main(){
  185. ////    freopen("difmax.inp" , "r" , stdin);
  186. ////    freopen("difmax.out" , "w" , stdout);
  187. //    faster;
  188. //    inp();
  189. //    solve();
  190. //    return 0;
  191. //}
  192.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FYUgdc
language:
C++14 (gcc 8.3)
created:
10 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!