[CodeChef BWGAME]Black-white Board Game
ao劲啊这题，，，
看到那个逆序对奇偶性就想到了行列式（考虑行列式的定义）……其实最后要判定的就是该矩阵行列式的正负性（或者是0）。
这个东西肯定可以高消搞成上三角，然后行列式就很好求了。但高消事\(O(n^3)\)的，会T掉。
考虑怎么去优化这个高消。首先在消元顺序合理的情况下，一定可以让矩阵在整个过程中一直是01矩阵。具体的实现方式，就是考虑从小到大对每个变量进行消元的时候，包含该变量的方程很多，并且他们两两之间一定是满足一个的全1段事另一个的前缀。那么用最短的那一段进行消元即可。
考虑到其他方程被消之后最靠左的1的位置会全部变成另一个位置，所以可以考虑使用可并堆维护各个方程。同时，为了求每个方程当前最靠左的1的位置，我搞了个并查集（逃
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <ext/pb_ds/priority_queue.hpp>
using R = double;
// using GG = __gnu_pbds::priority_queue<int>;
const int maxn = 100005;
const R eps = 1e-8;
inline int sign(R x) {
if(fabs(x) < eps) {
return 0;
} else {
if(x < 0.00) {
return -1;
} else {
return 1;
}
}
}
int seg[maxn][2];
namespace BF {
R A[105][105];
inline int det(int n) {
int flag = 1;
for(int i = 1; i <= n; i ++) {
int r = i;
for(int j = i + 1; j <= n; j ++) {
if(fabs(A[j][i]) > fabs(A[i][i])) {
r = j;
}
}
if(r != i) {
flag *= -1;
for(int j = i; j <= n; j ++) {
std::swap(A[i][j], A[r][j]);
}
} else {
if(sign(A[i][i]) == 0) {
return 0;
}
}
for(int j = i + 1; j <= n; j ++) {
if(sign(A[j][i]) == 0) continue;
double f = A[j][i] / A[i][i];
for(int k = i; k <= n; k ++) {
A[j][k] -= A[i][k] * f;
}
}
}
int ret = flag;
for(int i = 1; i <= n; i ++) {
ret *= sign(A[i][i]);
}
return ret;
}
inline void solve(int n) {
for(int i = 1; i <= n; i ++) {
int L = seg[i][0], R = seg[i][1];
for(int j = 1; j <= n; j ++) {
if(L <= j && j <= R) {
A[i][j] = 1;
} else {
A[i][j] = 0;
}
}
}
int v = (det(n));
if(v == -1) {
puts("Fedor");
} else if(v == 0) {
puts("Draw");
} else {
puts("Alex");
}
}
};
namespace CT {
/*
struct Node {
int l, r, id;
bool operator <(const Node &res) const {
if(l == res.l) {
if(r == res.r) {
return id < res.id;
} else {
return r < res.r;
}
} else {
return l < res.l;
}
}
bool operator >(const Node &res) const {
if(l == res.l) {
if(r == res.r) {
return id > res.id;
} else {
return r > res.r;
}
} else {
return l > res.l;
}
}
bool operator ==(const Node &res) const {
return (l == res.l) && (r == res.r) && (id == res.id);
}
};
*/
struct N2 {
int r, id;
N2() {
r = 0; id = 0;
}
N2(int x, int y) {
r = x; id = y;
}
bool operator <(const N2 &res) const {
if(r == res.r) {
return id < res.id;
} else {
return r < res.r;
}
}
bool operator >(const N2 &res) const {
if(r == res.r) {
return id > res.id;
} else {
return r > res.r;
}
}
bool operator ==(const N2 &res) const {
return (r == res.r) && (id == res.id);
}
};
/* struct Node {
Node *fa, *ch[2];
N2 v; int l;
int setv;
int d() {
return ((this == fa -> ch[1]) ? 1 : 0);
}
void sc(Node *c, int dir) {
ch[dir] = c;
c -> fa = this;
}
int cmp(const N2 &v2) const {
if(v == v2) {
return -1;
} else {
if(v2 < v) {
return 0;
} else {
return 1;
}
}
}
void paint(int x) {
if(l == -1) return;
l = x; setv = x;
}
void pushdown(int x) {
if(setv != -1) {
ch[0] -> paint(setv);
ch[1] -> paint(setv);
setv = -1;
}
}
};
Node pool[maxn]; std::queue<int> FQ;
Node *nil, *cur;
void init_pool() {
nil = cur = pool;
nil -> l = nil -> setv = -1;
nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
}
Node *alloc_node(N2 x, int L) {
Node *ret;
if(FQ.empty()) {
ret = ++ cur;
} else {
ret = FQ.front(); FQ.pop();
}
ret -> v = x;
ret -> l = L; ret -> setv = -1;
ret -> fa = ret -> ch[0] = ret -> ch[1] = nil;
return ret;
}
inline bool is_root(Node *o) {
return (o -> fa == nil)
}
inline void zig(Node *x) {
int d = x -> d(); Node *y = x -> fa;
if(is_root(y)) {
x -> fa = y -> fa;
} else {
y -> fa -> sc(x, y -> d());
}
y -> sc(x -> ch[d ^ 1], d);
x -> sc(y, d ^ 1);
}
void pdw_path(Node *x) {
if(!is_root(x)) pdw_path(x -> fa);
x -> pushdown();
}
inline void splay(Node *x) {
pdw_path(x);
while(!is_root(x)) {
Node *y = x -> fa;
if(!is_root(y)) {
if((x -> d()) ^ (y -> d())) {
zig(x);
} else {
zig(y);
}
}
zig(x);
}
}
Node *insert(Node *o, Node *x) {
if(o == nil) return x;
Node *last = o;
int d;
while(o != nil) {
o -> pushdown(); last = o;
d = o -> cmp(x -> v);
o = o -> ch[d];
}
x -> ch[0] = x -> ch[1] = nil;
last -> sc(x, d);
splay(x); return x;
}
Node *top(Node *x) {
Node *ret = x;
while(x -> ch[0] == 0) {
x -> paint
}
} */
int par[maxn * 2];
int get_fa(int x) {
if(par[x] == x) return x;
else return (par[x] = get_fa(par[x]));
}
void merge(int dir, int src) {
dir = get_fa(dir); src = get_fa(src);
if(dir == src) return;
par[src] = dir;
}
bool is_same(int x, int y) {
return (get_fa(x) == get_fa(y));
}
using heap = __gnu_pbds::priority_queue<N2, std::greater<N2> >;
heap Q[maxn];
int id[maxn], mp[maxn];
int det(int n) {
int flag = 1;
for(int i = 1; i <= n; i ++) {
Q[i].clear();
}
for(int i = 1; i <= 2 * n; i ++) {
par[i] = i;
}
for(int i = 1; i <= n; i ++) {
id[i] = mp[i] = i;
int L = seg[i][0], R = seg[i][1];
Q[L].push(N2(R, i));
merge(L, n + i);
}
for(int i = 1; i <= n; i ++) {
if(Q[i].empty()) {
return 0;
}
int p = id[i];
if(!(get_fa(p + n) <= i && seg[p][1] == (Q[i].top()).r)) {
flag *= -1;
int np = (Q[i].top()).id;
#ifdef LOCAL
printf("Swaping %d and %d.\n", p, np);
#endif
int nv = mp[np];
std::swap(id[i], id[nv]);
std::swap(mp[np], mp[p]);
}
p = id[i];
Q[i].pop();
int r = seg[p][1];
if(Q[i].size() > 0 && (Q[i].top()).r == r) {
return 0;
}
if(r < n) {
Q[r + 1].join(Q[i]);
merge(r + 1, i);
}
}
return flag;
}
void solve(int n) {
int v = det(n);
if(v == -1) {
puts("Fedor");
} else if(v == 0) {
puts("Draw");
} else {
puts("Alex");
}
}
};
int main() {
int T; scanf("%d", &T);
while(T --) {
int n; scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
scanf("%d%d", &seg[i][0], &seg[i][1]);
}
if(n <= 100) {
BF::solve(n);
} else {
CT::solve(n);
}
}
return 0;
}
