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<int> s0,s1;
  34.      for(int i=0;i<n;i++)
  35.      {
  36.          if(s[i]=='0')
  37.          {
  38.              if(!s1.empty())
  39.              {
  40.                  int k=s1.top();
  41.                  v[i]=k;
  42.                  s1.pop();
  43.                  s0.push(k);
  44.              }
  45.              else
  46.              {
  47.                  s0.push(c);
  48.                  v[i]=c;
  49.                  c++;
  50.              }
  51.          }
  52.          else
  53.          {
  54.              if(!s0.empty())
  55.              {
  56.                  int k=s0.top();
  57.                  v[i]=k;
  58.                  s0.pop();
  59.                  s1.push(k);
  60.              }
  61.              else
  62.              {
  63.                  s1.push(c);
  64.                  v[i]=c;
  65.                  c++;
  66.              }
  67.          }
  68.      }
  69.      int m=*max_element(v.begin(),v.end());
  70.      cout<<m<<endl;
  71.      for(auto i:v)
  72.      cout<<i<<" ";
  73.      cout<<endl;
  74.  }
  75.  return 0;
  76. }
Success #stdin #stdout 0s 4376KB
comments (?)
stdin
copy 
1
4
1100
stdout
copy 
2
1 2 2 1
https://ideone.com/opM2RL
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!