ferinの競プロ帳

競プロについてのメモ

SRM658 div1 easy OddEvenTree

考えたこと

  • よくわからないので実験をする
  • ある頂点からOな頂点ならEOの列を反転した列になる
  • 距離が1ずれるんだからそれはそう
  • この条件で可能どうかの判定はできそうな気持ちになる
  • 条件を満たしていれば適当に構築してえい

サンプルが弱すぎるだろ
サンプルエスパー警戒なんだろうか

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class OddEvenTree {
   public:
   vector <int> getTree(vector <string> x)
  {
    int n = x.size();
    string s1 = x[0], s2 = "?";
    VI v1, v2;
    REP(i, n) {
      if(x[i] == s1) {
        v1.PB(i);
      } else {
        if(s2 == "?") s2 = x[i];
        if(x[i] == s2) v2.PB(i);
        else return {-1};
      }
    }

    REP(i, n) if(s1[i] == s2[i]) return {-1};
    REP(i, v2.size()) if(s1[v2[i]] != 'O') return {-1};
    if(s2 == "?") return {-1};

    VI ans;
    REP(i, v2.size()) {
      ans.PB(v1[0]);
      ans.PB(v2[i]);
    }
    // v2[0] と v1[i]
    FOR(i, 1, v1.size()) {
      ans.PB(v2[0]);
      ans.PB(v1[i]);
    }
    return ans;
  }
};