QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#353671 | #7857. (-1,1)-Sumplete | ucup-team3215 | WA | 1ms | 3580kb | C++20 | 2.6kb | 2024-03-14 14:46:12 | 2024-03-14 14:46:12 |
Judging History
answer
#include <algorithm>
#include <array>
#include <bitset>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
constexpr int N = 4032;
bitset<N> edge[2][N], ans[N], used[2], neg[2], u[N], dr, dc;
int rt[N], ct[N], br[N][2], bc[N][2], n;
template <bool col>
bool match(int i) {
for (int j = -1; (j = (edge[col][i] & neg[!col])._Find_next(j), j < N); ) {
edge[col][i][j] = 0;
edge[!col][j][i] = 1;
if (col) {
ans[j][i] = !ans[j][i];
neg[0][j] = ++rt[j] < 0;
} else {
ans[i][j] = !ans[i][j];
neg[1][j] = ++ct[j] < 0;
}
return 1;
}
used[col][i] = 0;
for (int j = -1; (j = (edge[col][i] & used[!col])._Find_next(j), j < N); ) {
if (!match<!col>(j)) continue;
edge[col][i][j] = 0;
edge[!col][j][i] = 1;
if (col) ans[j][i] = !ans[j][i];
else ans[i][j] = !ans[i][j];
return 1;
}
return 0;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; ++i) if (string s; cin >> s)
for (int j = 0; j < n; ++j) edge[1][j][i] = !(edge[0][i][j] = s[j] == '+'), br[i][1] += s[j] == '+', br[i][0] -= s[j] == '-', bc[j][1] += s[j] == '+', bc[j][0] -= s[j] == '-';
for (int i = 0; i < n; ++i) cin >> rt[i];
for (int i = 0; i < n; ++i) cin >> ct[i];
auto mark = [&](int i, int j, bool w) {
if (u[i][j]) return;
u[i][j] = 1;
if (edge[0][i][j] == w) ans[i][j] = 1;
br[i][1] -= edge[0][i][j], br[i][0] += !edge[0][i][j];
bc[j][1] -= edge[0][i][j], bc[j][0] += !edge[0][i][j];
if (edge[0][i][j] == w) rt[i] -= 2 * edge[0][i][j] - 1, ct[j] -= 2 * edge[0][i][j] - 1;
edge[0][i][j] = edge[1][j][i] = 0;
};
for (int ch = 1; ch--; ) {
for (int i = 0; i < n; ++i) if (!dr[i] && (rt[i] >= br[i][1] || rt[i] <= br[i][0])) if (dr[i] = ch = 1)
for (int j = 0; j < n; ++j) mark(i, j, rt[i] >= br[i][1]);
for (int i = 0; i < n; ++i) if (!dc[i] && (ct[i] >= bc[i][1] || ct[i] <= bc[i][0])) if (dc[i] = ch = 1)
for (int j = 0; j < n; ++j) mark(j, i, ct[i] >= bc[i][1]);
}
for (int i = 0; i < n; ++i) ct[i] = -ct[i], neg[0][i] = rt[i] < 0, neg[1][i] = ct[i] < 0;
for (int ch = 1; ch--; ) {
for (int i = 0; i < n; ++i) while (rt[i] > 0 && used[0][i] && match<0>(i)) --rt[i], ch = 1;
for (int j = 0; j < n; ++j) while (ct[j] > 0 && used[1][j] && match<1>(j)) --ct[j], ch = 1;
used[0].set();
used[1].set();
}
for (int i = 0; i < n; ++i) if (rt[i] || ct[i]) return cout << "No\n", 0;
cout << "Yes\n";
for (int i = 0; i < n; ++i, cout << '\n')
for (int j = 0; j < n; ++j) cout.put('0' + ans[i][j]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3580kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
No
result:
wrong answer Jury has the answer but participant has not