結果
問題 | No.2663 Zero-Sum Submatrices |
ユーザー | chirprush |
提出日時 | 2024-04-02 02:45:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 2,660 bytes |
コンパイル時間 | 671 ms |
コンパイル使用メモリ | 79,872 KB |
実行使用メモリ | 11,648 KB |
最終ジャッジ日時 | 2024-09-30 23:03:28 |
合計ジャッジ時間 | 1,834 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <map>#include <set>#include <algorithm>#include <cmath>typedef long long ll;template<typename T>void read_some(std::vector<T> &v, int N) {for (int i = 0; i < N; i++) {T a;std::cin >> a;v.push_back(a);}}int a[(1 << 12)][(1 << 12)] = {0};void construct_line(int i, int j, int n, bool horizontal) {for (int v = 0; v < (1 << (n + 1)); v++) {int place = v % 2 + 2 * (v / 4);int side = (v / 2) % 2;if (horizontal) {a[i + side][j + place] = v;} else {a[i + place][j + side] = v;}}}void add(int i, int j, int n, int m, int value) {// std::cout << "add(" << i << ", " << j << ", " << n << ", " << m << ", " << value << ")" << std::endl;for (int k = 0; k < (1 << n); k++) {for (int l = 0; l < (1 << m); l++) {a[i + k][j + l] += value;}}}void construct(int i, int j, int n, int m) {// std::cout << "construct(" << i << ", " << j << ", " << n << ", " << m << ")" << std::endl;if (n == 1) {construct_line(i, j, m, true);} else if (m == 1) {construct_line(i, j, n, false);} else {construct(i, j, n - 1, m - 1);construct(i, j + (1 << (m - 1)), n - 1, m - 1);add(i, j + (1 << (m - 1)), n - 1, m - 1, 1 << (m + n - 2));construct(i + (1 << (n - 1)), j, n - 1, m - 1);add(i + (1 << (n - 1)), j, n - 1, m - 1, 1 << (m + n - 1));construct(i + (1 << (n - 1)), j + (1 << (m - 1)), n - 1, m - 1);add(i + (1 << (n - 1)), j + (1 << (m - 1)), n - 1, m - 1, (1 << (m + n - 1)) + (1 << (m + n - 2)));}}int main() {int n, m;std::cin >> n >> m;construct(0, 0, n, m);for (int i = 0; i < (1 << n); i++) {for (int j = 0; j < (1 << m); j++) {std::cout << a[i][j] << " ";}std::cout << std::endl;}/*for (int i = 0; i < (1 << n); i++) {for (int j = 0; j < (1 << m); j++) {for (int k = i + 1; k < (1 << n); k++) {for (int l = j + 1; l < (1 << m); l++) {if (a[i][j] ^ a[i][l] ^ a[k][j] ^ a[k][l]) {std::cout << "Bad pair" << std::endl;std::cout << i << " " << j << " " << k << " " << l << std::endl;std::cout << a[i][j] << " " << a[i][l] << " " << a[k][j] << " " << a[k][l] << std::endl;goto end;}}}}}end:;*/return 0;}