QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#640377 | #5438. Half Mixed | wpoem | WA | 27ms | 3696kb | C++20 | 5.9kb | 2024-10-14 11:31:18 | 2024-10-14 11:31:19 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <stack>
#ifdef LOCAL
template <class T, size_t size = std::tuple_size<T>::value> std::string to_debug(T, std::string s = "") requires(not std::ranges::range<T>);
std::string to_debug(auto x) requires requires(std::ostream& os) { os << x; } { return static_cast<std::ostringstream>(std::ostringstream() << x).str(); }
std::string to_debug(std::ranges::range auto x, std::string s = "") requires(not std::is_same_v<decltype(x), std::string>) {
for (auto xi : x) { s += ", " + to_debug(xi); }
return "[" + s.substr(s.empty() ? 0 : 2) + "]";
}
template <class T, size_t size> std::string to_debug(T x, std::string s) requires(not std::ranges::range<T>) {
[&]<size_t... I>(std::index_sequence<I...>) { ((s += ", " + to_debug(get<I>(x))), ...); }(std::make_index_sequence<size>());
return "(" + s.substr(s.empty() ? 0 : 2) + ")";
}
#define debug(...) std::cerr << __LINE__ << ": (" #__VA_ARGS__ ") = " << to_debug(std::tuple(__VA_ARGS__)) << "\n"
#else
#define debug(x...)
#endif
using i64 = long long;
void solve()
{
#define tests
int n, m; std::cin >> n >> m;
if (8 * n * m > 1LL * n * m * (n + 1) * (m + 1) or (1LL * (n + 1) * (m + 1) * n * m) % 8 != 0) {std::cout << "No\n"; return ;}
i64 tot{1LL * n * m * (n + 1) * (m + 1) / 4};//所有子矩阵个数
i64 pure_one{1LL * n * m};
auto calc = [&](int n, int m) {
if (n <= 0 or m <= 0) {return 0LL;}
return 1LL * n * m * (n + 1) * (m + 1) / 4 - 1LL * n * m;
};
do {//先选一了第一列,然后再选一列,然后算贡献
i64 rem{tot - pure_one};//所有子矩阵减去大小为1的子矩阵
//先处理接在一起的状况
//1 1 0 0 0 0 0
//1 0 1 0 0 0 0
//1 0 1 0 0 0 0
//0 1 2 3 4 5 6
//1 0 0 1 0 0 0
//1 0 0 1 0 0 0
int d = 1;
i64 delta{calc(n, 2) + calc(n, m - d - 1)};
i64 mixed{rem - delta}, pure{pure_one + delta};
if (d == m - 1) {debug(mixed, pure);}
if (mixed == pure) {
std::cout << "Yes\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j == 0 or j == d) {
std::cout << "1 ";
} else {
std::cout << "0 ";
}
}
std::cout << "\n";
}
return ;
}
for (int d = 2; d < m; d++) {
i64 delta{calc(n, 1) + calc(n, 1) + calc(n, d - 1) + calc(n, m - d - 1)};
i64 mixed{rem - delta}, pure{pure_one + delta};
if (mixed == pure) {
std::cout << "Yes\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j == 0 or j == d) {
std::cout << "1 ";
} else {
std::cout << "0 ";
}
}
std::cout << "\n";
}
return ;
}
}
} while (false);
do {//先选一了第一行,然后再选一行,然后算贡献
i64 rem{tot - pure_one};//所有子矩阵减去大小为1的子矩阵
//先处理接在一起的状况
//1 1 0 0 0 0 0
//1 0 1 0 0 0 0
//1 0 1 0 0 0 0
//0 1 2 3 4 5 6
//1 0 0 1 0 0 0
//1 0 0 1 0 0 0
int d = 1;
i64 delta{calc(2, m) + calc(n - 1 - d, m)};
i64 mixed{rem - delta}, pure{pure_one + delta};
if (mixed == pure) {
std::cout << "Yes\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 or i == d) {
std::cout << "1 ";
} else {
std::cout << "0 ";
}
}
std::cout << "\n";
}
return ;
}
for (int d = 2; d < n; d++) {
i64 delta{calc(1, m) + calc(1, m) + calc(d - 1, m) + calc(n - 1 - d, m)};
i64 mixed{rem - delta}, pure{pure_one + delta};
if (mixed == pure) {
std::cout << "Yes\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 or i == d) {
std::cout << "1 ";
} else {
std::cout << "0 ";
}
}
std::cout << "\n";
}
return ;
}
}
} while (false);
do {//先选一了第一列,然后再选一列,然后算贡献
i64 rem{tot - pure_one};//所有子矩阵减去大小为1的子矩阵
//先处理接在一起的状况
//1 1 0 0 0 0 0
//1 0 1 0 0 0 0
//1 0 1 0 0 0 0
//0 1 2 3 4 5 6
//1 0 0 1 0 0 0
//1 0 0 1 0 0 0
for (int d = 0; d < m; d++) {
i64 delta{calc(n, 1) + calc(n, d) + calc(n, m - d - 1)};
i64 mixed{rem - delta}, pure{pure_one + delta};
if (mixed == pure) {
std::cout << "Yes\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j == d) {
std::cout << "1 ";
} else {
std::cout << "0 ";
}
}
std::cout << "\n";
}
return ;
}
}
} while (false);
do {//先选一了第一行,然后再选一行,然后算贡献
i64 rem{tot - pure_one};//所有子矩阵减去大小为1的子矩阵
//先处理接在一起的状况
//1 1 0 0 0 0 0
//1 0 1 0 0 0 0
//1 0 1 0 0 0 0
//0 1 2 3 4 5 6
//1 0 0 1 0 0 0
//1 0 0 1 0 0 0
for (int d = 0; d < n; d++) {
i64 delta{calc(1, m) + calc(d, m) + calc(n - d - 1, m)};
i64 mixed{rem - delta}, pure{pure_one + delta};
if (mixed == pure) {
std::cout << "Yes\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == d) {
std::cout << "1 ";
} else {
std::cout << "0 ";
}
}
std::cout << "\n";
}
return ;
}
}
} while (false);
std::cout << "No\n";
}
signed main()
{
std::cin.tie(nullptr)->sync_with_stdio(false);
int _{1};
#ifdef tests
std::cin >> _;
#endif
while(_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
input:
2 2 3 1 1
output:
Yes 1 0 1 1 0 1 No
result:
ok OK, Accepted. (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 27ms
memory: 3696kb
input:
5382 1 1 1 2 2 1 1 3 2 2 3 1 1 4 2 3 3 2 4 1 1 5 2 4 3 3 4 2 5 1 1 6 2 5 3 4 4 3 5 2 6 1 1 7 2 6 3 5 4 4 5 3 6 2 7 1 1 8 2 7 3 6 4 5 5 4 6 3 7 2 8 1 1 9 2 8 3 7 4 6 5 5 6 4 7 3 8 2 9 1 1 10 2 9 3 8 4 7 5 6 6 5 7 4 8 3 9 2 10 1 1 11 2 10 3 9 4 8 5 7 6 6 7 5 8 4 9 3 10 2 11 1 1 12 2 11 3 10 4 9 5 8 6 ...
output:
No No No Yes 1 0 1 No Yes 1 0 1 Yes 1 0 0 1 Yes 1 0 1 1 0 1 Yes 1 1 0 0 1 1 Yes 1 0 0 1 No Yes 1 0 0 1 1 0 0 1 Yes 1 0 1 1 0 1 1 0 1 Yes 1 1 0 0 0 0 1 1 No No No Yes 1 0 0 1 1 0 0 1 1 0 0 1 Yes 1 0 1 1 0 1 1 0 1 1 0 1 No No Yes 0 0 1 0 0 0 0 No Yes 1 1 1 1 1 0 0 0 0 0...
result:
wrong answer Wrong Verdict (test case 106)