Advertisement
Guest User

Untitled

a guest
Dec 29th, 2019
2,787
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.98 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <bits/stdc++.h>
  3. /*
  4. #pragma GCC target ("avx2")
  5. #pragma GCC optimization ("O3")
  6. #pragma GCC optimization ("unroll-loops")*/
  7.  
  8. using namespace std;
  9.  
  10. #define ll long long
  11. #define ld long double
  12. #define mp make_pair
  13.  
  14.  
  15. ll solve1 (string s)
  16. {
  17.  
  18. int n = s.size();
  19. int m = sqrt(n);
  20.  
  21. vector<int> pos_one;
  22. for (int i = 0; i<n; i++) if (s[i]=='1') pos_one.push_back(i);
  23. if (pos_one.size()==0) return 0;
  24.  
  25. pos_one.push_back(n);
  26.  
  27.  
  28. vector<int> cnt(n*m+n);
  29.  
  30.  
  31. ll total = 0;
  32. for (ll i = 1; i<=m; i++)
  33. {
  34. int cur = 0;
  35. cnt[i*n]++;
  36. for (int j = 1; j<=n; j++)
  37. {
  38. if (s[j-1]=='1') cur++;
  39. int idx = j - i*cur;
  40. total+=cnt[idx+i*n];
  41. cnt[idx+i*n]++;
  42. }
  43.  
  44. cur = 0;
  45. cnt[i*n]--;
  46. for (int j = 1; j<=n; j++)
  47. {
  48. if (s[j-1]=='1') cur++;
  49. int idx = j - i*cur;
  50. cnt[idx+i*n]--;
  51. }
  52. }
  53.  
  54.  
  55. vector<int> idx(n, -1);
  56. int cur = 0;
  57. for (int i = 0; i<n; i++)
  58. {
  59. idx[i] = cur;
  60. if (s[i]=='1') cur++;
  61. }
  62.  
  63. for (int i = 0; i<n; i++)
  64. {
  65. for (ll j = 1; j<=n/m&&idx[i]+j<=cur; j++)
  66. {
  67.  
  68. ll l = pos_one[idx[i]+j-1] - i + 1;
  69. ll r = pos_one[idx[i]+j] - i;
  70. l = max(l, j*(m+1));
  71. if (l<=r) total+=r/j - (l-1)/j;
  72. }
  73. }
  74. return total;
  75. }
  76.  
  77. ll solve2(string s)
  78. {
  79. int n = s.size();
  80. vector<int> pref(n+1);
  81. for (int i = 1; i<=n; i++)
  82. {
  83. pref[i] = pref[i-1];
  84. if (s[i-1]=='1') pref[i]++;
  85. }
  86. ll cnt = 0;
  87. for (int i = 0; i<n; i++)
  88. for (int j = i+1; j<=n; j++)
  89. {
  90. if ((pref[j]>pref[i])&&((j-i)%(pref[j]-pref[i])==0)) cnt++;
  91. }
  92. return cnt;
  93. }
  94.  
  95. int main() {
  96. ios_base::sync_with_stdio(0);
  97. cin.tie(nullptr);
  98.  
  99. string s;
  100. cin>>s;
  101. cout<<solve1(s);
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement