fork download
  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
stdin
4
4
0011
6
111111
5
10101
8
01010000
stdout
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