Guest User

C1. Prefix Flip(Easy Version)

a guest
Jul 22nd, 2020
85
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl "\n"
  4. typedef long long ll;
  5. typedef long double ld;
  6.  
  7. void operation(string &s, int j)
  8. {
  9.     for(int i=0;i<j;i++)
  10.     {
  11.         if(s[i]=='1')
  12.             s[i]='0';
  13.         else
  14.             s[i]='1';
  15.     }
  16.     reverse(s.begin(), s.begin()+j);
  17. }
  18.  
  19. void solve()
  20. {
  21.     int n;
  22.     cin>>n;
  23.     string s, t;
  24.     cin>>s>>t;
  25.     //convert s into t
  26.     int j=n-1;
  27.     while(s[j]==t[j])
  28.         j--;
  29.     vector<int> ans;
  30.     while(j>=0)
  31.     {
  32.         if(s[0]!=t[j])
  33.         {
  34.             operation(s, j+1);
  35.  
  36.             ans.push_back(j+1);
  37.             while(s[j]==t[j])
  38.                 --j;
  39.         }
  40.         else
  41.         {
  42.             ans.push_back(1);
  43.             if(s[0]=='0')
  44.                 s[0]='1';
  45.             else
  46.                 s[0]='1';
  47.             operation(s, j+1);
  48.             ans.push_back(j+1);
  49.             while(s[j]==t[j])
  50.                 --j;
  51.         }
  52.    
  53.     }
  54.  
  55.     if(ans.size()==0){
  56.         cout<<0<<endl;
  57.         return;
  58.     }
  59.     cout<<ans.size()<<" ";
  60.     for(auto x:ans)
  61.         cout<<x<<" ";
  62.     cout<<endl;
  63.  
  64. }
  65.  
  66. int main() {
  67. ios_base::sync_with_stdio(false);
  68. cin.tie(NULL);
  69. int t;
  70. cin>>t;
  71. while(t--)
  72. {
  73.     solve();
  74. }
  75.  
  76.  
  77. return 0;
  78. }
RAW Paste Data