NJXZCOJ 844 集训队日常之BigBaiZhou玩游戏
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 #include <bitset> 15 16 using namespace std; 17 18 typedef long long ll; 19 typedef pair<int, int> pii; 20 const int maxn = 1e3 + 10; 21 int n, m, a; 22 int G[maxn][maxn], c[maxn * maxn]; 23 vector<int> v; 24 25 int lowbit(int x) { return x & (-x); } 26 void update(int x) { 27 while (x < maxn * maxn) { ++c[x]; x += lowbit(x); } 28 } 29 int query(int x) { 30 int ret = 0; 31 while (x > 0) { ret += c[x]; x -= lowbit(x); } 32 return ret; 33 } 34 35 int main() { 36 #ifdef __AiR_H 37 freopen("A.in", "r", stdin); 38 // freopen("out.txt", "w", stdout); 39 #endif // __AiR_H 40 while (scanf("%d %d", &n, &m) != EOF) { 41 if (n == 0 && m == 0) { break; } v.clear(); int t; 42 for (int i = 1; i <= n; ++i) { 43 for (int j = 1; j <= m; ++j) { 44 scanf("%d", &a); 45 if (a == 0) { t = (n - i) + (m - j); t %= 2; v.push_back(n * m); } 46 else { v.push_back(a); } 47 } 48 } 49 int Size = v.size(); memset(c, 0, sizeof(c)); ll sum = 0; 50 for (int i = 0; i < Size; ++i) { 51 sum += i - query(v[i]); update(v[i]); 52 } 53 // printf("%lld ", sum); 54 if (sum % 2 == t) { printf("YES "); } else { printf("NO "); } 55 } 56 return 0; 57 }