CODE FESTIVAL 2016 Final

Submission #994519

Source codeソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

const int mod = 1e9 + 7;

int add(int x, int y) {
  x += y;
  if (x >= mod)
    x -= mod;
  return x;
}

int udd(int &x, int y) {
  return x = add(x, y);
}

int sub(int x, int y) {
  return add(x, mod - y);
}

int mul(ll x, ll y) {
  return x * y % mod;
}

int uul(int &x, int y) {
  return x = mul(x, y);
}

const int M = 239;
const int N = 103 * 103;

bitset<N> b[M];
int low[M];
int m = 0;

void add(bitset<N> x) {
  for (int i = 0; i < m; ++i)
    if (x[low[i]]) {
      x ^= b[i];
    }
  
  if (x.count()) {
    b[m] = x;
    for (int i = 0; i < N; ++i)
      if (x[i]) {
        low[m] = i;
        break;
      }
    ++m;
  }
}

int h, w;
string s[M];
int ans = 1;
bool u[M][M];


bool isPal(string s) {
  int n = s.length();
  for (int i = 0; i < n; ++i)
    if (s[i] != s[n - 1 - i])
      return false;
  return true;
}

int perm(string s) {
  set<string> ans;
  for (int i = 0; i < 24; ++i) {
    ans.insert(s);
    next_permutation(s.begin(), s.end());
  }
  //cout << "s = " << s << endl;
  //cout << "sz = " << ans.size() << endl;
  return ans.size();
}

void read() {
  cin >> h >> w;
  for (int i = 0; i < h; ++i)
    cin >> s[i];

  if (h % 2 == 1) {
    if (!isPal(s[h / 2]))
      uul(ans, 2);
  }

  if (w % 2 == 1) {
    string cur = "";
    for (int i = 0; i < h; ++i)
      cur.push_back(s[i][w / 2]);
    if (!isPal(cur))
      uul(ans, 2);
  }
}

void kill() {
  for (int i = 0; i < h - 1 - i; ++i)
    for (int j = 0; j < w - 1 - j; ++j) {
      string cur = "";
      for (int a : {i, h - i - 1})
        for (int b : {j, w - j - 1})
            cur.push_back(s[a][b]);

      int sz = perm(cur);
      if (sz == 24) {
        u[i][j] = true;
        uul(ans, 12);
      } else {
        uul(ans, sz);
      }
    }

  for (int i = 0; i < h - i - 1; ++i) {
    bitset<N> x;
    for (int j = 0; j < w - 1 - j; ++j)
      if (u[i][j]) {
        x[i * 102 + j] = 1;
      }
    add(x);
  }

  for (int j = 0; j < w - 1 - j; ++j) {
    bitset<N> x;
    for (int i = 0; i < h - 1 - i; ++i)
      if (u[i][j])
        x[i * 102 + j] = 1; 
    add(x);
  }

  for (int i = 0; i < m; ++i)
    uul(ans, 2);

  cout << ans << endl;
}

int main() {
#ifdef LOCAL
  assert(freopen("i.in", "r", stdin));
#endif

  ios_base::sync_with_stdio(false);

  read();
  kill();
}

Submission

Task問題 I - Reverse Grid
User nameユーザ名 Arterm
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1900
Source lengthソースコード長 2531 Byte
File nameファイル名
Exec time実行時間 39 ms
Memory usageメモリ使用量 640 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
all 1900 / 1900 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt,01-31.txt,01-32.txt,01-33.txt,01-34.txt,01-35.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 3 ms 256 KB
01-02.txt AC 3 ms 256 KB
01-03.txt AC 3 ms 256 KB
01-04.txt AC 3 ms 256 KB
01-05.txt AC 3 ms 256 KB
01-06.txt AC 3 ms 256 KB
01-07.txt AC 3 ms 256 KB
01-08.txt AC 3 ms 256 KB
01-09.txt AC 3 ms 256 KB
01-10.txt AC 11 ms 256 KB
01-11.txt AC 17 ms 256 KB
01-12.txt AC 18 ms 256 KB
01-13.txt AC 11 ms 256 KB
01-14.txt AC 10 ms 384 KB
01-15.txt AC 12 ms 512 KB
01-16.txt AC 39 ms 640 KB
01-17.txt AC 38 ms 640 KB
01-18.txt AC 39 ms 640 KB
01-19.txt AC 28 ms 640 KB
01-20.txt AC 28 ms 640 KB
01-21.txt AC 28 ms 640 KB
01-22.txt AC 4 ms 384 KB
01-23.txt AC 18 ms 512 KB
01-24.txt AC 32 ms 640 KB
01-25.txt AC 31 ms 640 KB
01-26.txt AC 32 ms 640 KB
01-27.txt AC 5 ms 384 KB
01-28.txt AC 8 ms 384 KB
01-29.txt AC 4 ms 384 KB
01-30.txt AC 9 ms 384 KB
01-31.txt AC 39 ms 640 KB
01-32.txt AC 39 ms 640 KB
01-33.txt AC 38 ms 640 KB
01-34.txt AC 38 ms 640 KB
01-35.txt AC 38 ms 640 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 3 ms 256 KB