Submission #10689686


Source Code Expand

Copy
// #define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

const int N = 1 << 10;
int a[N][N], b[N][N], pre[N][N];

int solve(int a[N][N], int n, int m) {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + a[i][j];
    }
  }
  int ret = 0;
  for (int x1 = 0; x1 < n; ++x1) {
    for (int x2 = x1 + 1; x2 <= n; ++x2) {
      for (int y1 = 0; y1 < m; ++y1) {
        for (int y2 = y1 + 1; y2 <= m; ++y2) {
          int cnt = pre[x2][y2] - pre[x1][y2] - pre[x2][y1] + pre[x1][y1];
          if (cnt % 2) ++ret;
        }
      }
    }
  }
  return ret;
}

void doit(int a[N][N], int u, int v, int n, int m) {
  if (n == 1 && m == 1) return;
  a[u + n / 2][v + m / 2] = 1;
  // if (m > 1) {
  //   for (int i = 0; i < n; ++i) {
  //     a[u + i][v + m / 2] = 1;
  //   }
  // }
  // if (n > 1) {
  //   for (int i = 0; i < m; ++i) {
  //     a[u + n / 2][v + i] = 1;
  //   }
  // }
  if (n > 1 && m > 1) {
    doit(a, u, v, n / 2, m / 2);
    doit(a, u + n / 2 + 1, v, n / 2, m / 2);
    doit(a, u, v + m / 2 + 1, n / 2, m / 2);
    doit(a, u + n / 2 + 1, v + m / 2 + 1, n / 2, m / 2);
  } else if (n == 1) {
    doit(a, u, v, n, m / 2);
    doit(a, u, v + m / 2 + 1, n, m / 2);
  } else {
    doit(a, u, v, n / 2, m);
    doit(a, u + n / 2 + 1, v, n / 2, m);
  }
}

int main() {
  int n, m;
  cin >> n >> m;
  n = (1 << n) - 1;
  m = (1 << m) - 1;
  // for (int i = 0; i < n; ++i) {
  //   for (int j = 0; j < m; ++j) {
  //     a[i][j] = 0;
  //   }
  // }
  doit(a, 0, 0, n, m);
  // int A = solve(a, n, m);
  // for (int i = 0; i < n; ++i) {
  //   for (int j = 0; j < m; ++j) {
  //     b[i][j] = 1 - a[i][j];
  //   }
  // }
  // int B = solve(b, n, m);
  // trace(A, B);
  // if (A > B) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        printf("%d", a[i][j]);
      }
      puts("");
    }
  // } else {
  //   for (int i = 0; i < n; ++i) {
  //     for (int j = 0; j < m; ++j) {
  //       printf("%d", a[i][j]);
  //     }
  //     puts("");
  //   }
  // }
  return 0;
  n = 3; m = 3;
  int len = n * m, best = 0;
  for (int k = 0; k < (1 << len); ++k) {
    for (int i = 0; i < len; ++i) {
      int x = i / m, y = i % m;
      if (k & (1 << i)) {
        a[x][y] = 1;
      } else {
        a[x][y] = 0;
      }
    }
    int cur = solve(a, n, m);
    best = max(best, cur);
  }
  trace(best);
  for (int k = 0; k < (1 << len); ++k) {
    for (int i = 0; i < len; ++i) {
      int x = i / m, y = i % m;
      if (k & (1 << i)) {
        a[x][y] = 1;
      } else {
        a[x][y] = 0;
      }
    }
    int cur = solve(a, n, m);
    if (cur == best) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
          cout << a[i][j];
        }
        cout << endl;
      }
      cout << endl;
    }
  }
  trace(best);
  return 0;
}

Submission Info

Submission Time
Task E - Odd Sum Rectangles
User cuiaoxiang
Language C++14 (GCC 5.4.1)
Score 0
Code Size 5124 Byte
Status WA
Exec Time 78 ms
Memory 5376 KB

Judge Result

Set Name All sample
Score / Max Score 0 / 900 0 / 0
Status
AC × 13
WA × 4
AC × 1
Set Name Test Cases
All 00_sample_01, 02_random_01, 02_random_02, 02_random_03, 02_random_04, 02_random_05, 02_random_06, 02_random_07, 02_random_08, 02_random_09, 02_random_10, 02_random_11, 02_random_12, 02_random_13, 02_random_14, 02_random_15, 02_random_16
sample 00_sample_01
Case Name Status Exec Time Memory
00_sample_01 AC 2 ms 2304 KB
02_random_01 WA 1 ms 256 KB
02_random_02 AC 2 ms 2304 KB
02_random_03 AC 2 ms 2304 KB
02_random_04 AC 2 ms 2304 KB
02_random_05 AC 2 ms 4352 KB
02_random_06 WA 78 ms 5376 KB
02_random_07 AC 40 ms 4864 KB
02_random_08 AC 40 ms 4864 KB
02_random_09 AC 11 ms 2432 KB
02_random_10 AC 21 ms 4608 KB
02_random_11 AC 2 ms 2304 KB
02_random_12 AC 2 ms 2304 KB
02_random_13 AC 2 ms 2304 KB
02_random_14 AC 2 ms 2304 KB
02_random_15 WA 2 ms 2304 KB
02_random_16 WA 2 ms 2304 KB