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; } };