fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. vector<int> p(int maxVal) {
  7.     vector<int> divCount(maxVal+1, 0);
  8.     for (int d = 1; d <= maxVal; d++){
  9.         for (int m = 2*d; m <= maxVal; m += d){
  10.             divCount[m]++;
  11.         }
  12.     }
  13.     return divCount;
  14. }
  15.  
  16. int main(){
  17.     ios::sync_with_stdio(false);
  18.     cin.tie(nullptr);
  19.  
  20.     int tc;
  21.     cin >> tc;
  22.     const int MAX_N = 1000000;
  23.     vector<int> divCount = p(MAX_N);
  24.  
  25.     while(tc--){
  26.         int n;
  27.         cin >> n;
  28.         string s;
  29.         cin >> s;
  30.         int r = 0;
  31.         char last = '\0';
  32.  
  33.         for (int i = 0; i < n; i++){
  34.             if(i == 0 || s[i] != last){
  35.                 r++;  
  36.             }
  37.             last = s[i];
  38.  
  39.             int L = i + 1;
  40.             int t = r - 1; 
  41.             int countValid = 0;
  42.  
  43.             countValid += (L - t);
  44.  
  45.             if(r >= 2) {
  46.                 countValid += divCount[r];
  47.             }
  48.  
  49.             cout << countValid << (i+1 == n ? "\n" : " ");
  50.         }
  51.     }
  52.     return 0;
  53. }
Success #stdin #stdout 0.04s 7052KB
comments (?)
stdin
copy 
3
5
00011
10
0101010101
7
0010100
stdout
copy 
1 2 3 4 5
1 2 2 3 2 4 2 4 3 4
1 2 3 3 4 3 4
https://ideone.com/wW6SsY
language:
C++ (gcc 8.3)
created:
7 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!