Guest User

Div2D

a guest
Dec 14th, 2019
209
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // #pragma GCC optimize("O3")
  2. // #pragma GCC optimize("unroll-loops")
  3. // #pragma comment(linker,"/stack:200000000")
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. #define DEBUG
  8. #ifndef DEBUG
  9.     #define endl "\n"
  10. #endif
  11.  
  12. #define PI 2*acos(0.0)
  13. #define INFLL 1e18
  14. #define CLEAR(x,val) memset(x,val,sizeof(x))
  15. #define print(x) cout << x << endl, exit(0)
  16. #define watch(x) cerr << #x << " -> " << x << endl
  17. // #define int long long
  18.  
  19. typedef long long ll;
  20. typedef long double ld;
  21. typedef pair<int,int> pii;
  22.  
  23. const int INF = 1000000000;
  24. const int MOD = 1000000007; //998244353
  25.  
  26. const int dx[]= {1,0,-1,0,1,-1,1,-1};
  27. const int dy[]= {0,1,0,-1,1,1,-1,-1};
  28.  
  29. void show(const vector<int> &vec) {
  30.     cout << vec.size() << endl;
  31.     for(int val : vec)
  32.         cout << val << " "; cout << endl;
  33. }
  34.  
  35. signed main()
  36. {  
  37.     //freopen("","r",stdin);
  38.     //freopen("","w",stdout);
  39.     cin.tie(0), cout.tie(0);
  40.     ios::sync_with_stdio(0);
  41.     int q;
  42.     cin >> q;
  43.     while(q--) {
  44.         int n;
  45.         cin >> n;
  46.         int a = 0, b = 0, c = 0, d = 0;
  47.         vector<string> v(n);
  48.         map<string,bool> mp;
  49.         for(int i = 0; i < n; i++) {
  50.             cin >> v[i];
  51.             mp[v[i]] = true;
  52.             if(v[i][0] == '0' && v[i].back() == '0')
  53.                 ++a;
  54.             if(v[i][0] == '0' && v[i].back() == '1')
  55.                 ++b;
  56.             if(v[i][0] == '1' && v[i].back() == '0')
  57.                 ++c;
  58.             if(v[i][0] == '1' && v[i].back() == '1')
  59.                 ++d;
  60.         }
  61.         if(b == 0 && c == 0) {
  62.             if(!(a && d))
  63.                 cout << 0 << endl;
  64.             else
  65.                 cout << -1 << endl;
  66.         }
  67.         else {
  68.             vector<int> res;
  69.             if(b > c) {
  70.                 for(int i = 0; i < n && abs(b-c)>1; i++) {
  71.                     if(v[i][0] == '0' && v[i].back() == '1') {
  72.                         string str = v[i];
  73.                         reverse(str.begin(), str.end());
  74.                         if(!mp[str]) {
  75.                             res.push_back(i+1);
  76.                             --b, ++c;
  77.                         }
  78.                     }
  79.                 }
  80.             } else {
  81.                 for(int i = 0; i < n && abs(c-b)>1; i++) {
  82.                     if(v[i][0] == '1' && v[i].back() == '0') {
  83.                         string str = v[i];
  84.                         reverse(str.begin(), str.end());
  85.                         if(!mp[str]) {
  86.                             res.push_back(i+1);
  87.                             --c, ++b;
  88.                         }
  89.                     }
  90.                 }
  91.             }
  92.             if(abs(b-c) > 1)
  93.                 cout << "-1" << endl;
  94.             else
  95.                 show(res);
  96.         }
  97.     }  
  98.     return 0;
  99. }
RAW Paste Data