POJ_2893_TLE_2.cpp

#include <iostream>
#include <vector>
using namespace std;

class SlidingPuzzle {
private:
  vector<int> bitree;
  int lowbit(int x) {
    return x & (-x);
  }
  void insertBIT(int x, int n) {
    while (x < n) {
      bitree[x]++;
      x += lowbit(x);
    }
  }
  int countLowerBIT(int x) {
    int result = 0;
    while (x) {
      result += bitree[x];
      x -= lowbit(x);
    }
    return result;
  }
  int inversions(vector<int>& board) {
    int result = 0;
    int n = board.size() + 1;
    for (int i = 0; i < n; ++i) {
      bitree[i] = 0;
    }
    for (int i = 0; i < board.size(); ++i) {
      insertBIT(board[i], n);
      result += i + 1 - countLowerBIT(board[i]);
    }
    return result;
  }
public:
  SlidingPuzzle () {
    bitree.resize(2000);
  }
  bool checkSolvablility(vector<int>& board, int n, int m, int zeropos) {
    int inv = inversions(board);
    if (m & 1) {
      return (inv & 1) == 0;
    }
    // even m
    int zeroy = zeropos / m;
    int ydistance = n - zeroy;
    return (inv ^ ydistance) & 1;
  }
};

int main() {
  int n;
  int m;
  cin >> n >> m;
  SlidingPuzzle puzzle;
  while (n != 0 && m != 0) {
    int size = n * m;
    vector<int> board(size - 1);
    int pos = 0;
    int zeropos = 0;
    for (int i = 0; i < size; ++i) {
      int x;
      cin >> x;
      if (x == 0) {
        zeropos = i;
      } else {
        board[pos++] = x;
      }
    }
    bool result = puzzle.checkSolvablility(board, n, m, zeropos);
    cout << (result ? "YES" : "NO") << endl;
    cin >> n >> m;
  }
  return 0;
}