fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int      long long int
  3. #define nitro    ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
  4. #define pb       push_back
  5. #define pi       3.1415926535897932384626
  6. #define mod      1000000007
  7. #define endl     '\n'
  8. #define DEBUG    false
  9. #define F        first
  10. #define S        second
  11. #pragma GCC optimize "trapv"
  12.  
  13. using namespace std;
  14.  
  15.  
  16. int32_t main()
  17. {
  18.  nitro;
  19.  /*#ifndef ONLINE_JUDGE
  20.       freopen("input.txt","r",stdin);
  21.       freopen("output.txt","w",stdout);
  22.  #endif*/
  23.  int t;
  24.  cin>>t;
  25.  while(t--)
  26.  {
  27.      int n;
  28.      cin>>n;
  29.      string s;
  30.      cin>>s;
  31.      int c=1;
  32.      std::vector<int> v(n,0);
  33.      std::stack<pair<char,int>> st1,st2;
  34.      st1.push({s[0],c});
  35.      v[0]=c;
  36.      for(int i=1;i<n;i++)
  37.      {
  38.          if(s[i]=='0')
  39.          {
  40.              if(st1.top().F=='1')
  41.              {
  42.                  int k=st1.top().S;
  43.                  st1.push({s[i],k});
  44.                  v[i]=k;
  45.              }
  46.              else if(st2.size()==0)
  47.              {
  48.                  c++;
  49.                  st2.push({s[i],c});
  50.                  v[i]=c;
  51.              }
  52.              else if(st2.top().F=='1')
  53.              {
  54.                  int k=st2.top().S;
  55.                  st2.push({s[i],k});
  56.                  v[i]=k;
  57.              }
  58.              else
  59.              {
  60.                  c++;
  61.                  v[i]=c;
  62.              }
  63.          }
  64.          else
  65.          {
  66.              if(st1.top().F=='0')
  67.              {
  68.                  int k=st1.top().S;
  69.                  st1.push({s[i],k});
  70.                  v[i]=k;
  71.              }
  72.              else if(st2.size()==0)
  73.              {
  74.                  c++;
  75.                  st2.push({s[i],c});
  76.                  v[i]=c;
  77.              }
  78.              else if(st2.top().F=='0')
  79.              {
  80.                  int k=st2.top().S;
  81.                  st2.push({s[i],k});
  82.                  v[i]=k;
  83.              }
  84.              else
  85.              {
  86.                  c++;
  87.                  v[i]=c;
  88.              }
  89.          }
  90.      }
  91.      cout<<c<<endl;
  92.      for(auto i:v)
  93.      cout<<i<<" ";
  94.      cout<<endl;
  95.  }
  96.  return 0;
  97. }
Success #stdin #stdout 0s 4504KB
comments (?)
stdin
copy 
4
4
0011
6
111111
5
10101
8
01010000
stdout
copy 
2
1 2 1 2 
6
1 2 3 4 5 6 
1
1 1 1 1 1 
4
1 1 1 1 1 2 3 4
https://ideone.com/yXMA6y
language:
C++14 (gcc 8.3)
created:
3 years 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!