QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#405523 | #7857. (-1,1)-Sumplete | dnialh# | WA | 1ms | 3500kb | C++23 | 3.9kb | 2024-05-06 03:53:13 | 2024-05-06 03:53:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define sq(a) ((a)*(a))
#define per(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rep(i,a,b) for (int i=a; i<b; i++)
#define FOR(i,a,b) for (int i=a; i<b; i++)
#define F0R(i,a) for (int i=0; i<a; i++)
#define ROF(i,a,b) for (int i = (b)-1; i >= a; i--)
#define R0F(i,a) for (int i = (a)-1; i >= 0; i--)
#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << endl, 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << endl;
#define _ << " _ " <<
#define ll int
using vi = vector<int>;
using vvi = vector<vi>;
struct Dinic {
struct Edge {
int to, rev;
ll c, oc;
ll flow() { return max(oc - c, 0); } // if you need flows
};
vi lvl, ptr, q;
vector<vector<Edge>> adj;
Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
void addEdge(int a, int b, ll c, ll rcap = 0) {
adj[a].push_back({b, sz(adj[b]), c, c});
adj[b].push_back({a, sz(adj[a]) - 1, rcap, rcap});
}
ll dfs(int v, int t, ll f) {
if (v == t || !f) return f;
for (int& i = ptr[v]; i < sz(adj[v]); i++) {
Edge& e = adj[v][i];
if (lvl[e.to] == lvl[v] + 1)
if (ll p = dfs(e.to, t, min(f, e.c))) {
e.c -= p, adj[e.to][e.rev].c += p;
return p;
}
}
return 0;
}
ll calc(int s, int t) {
ll flow = 0; q[0] = s;
rep(L,30,31) do { // 'int L=30' maybe faster for random data
lvl = ptr = vi(sz(q));
int qi = 0, qe = lvl[s] = 1;
while (qi < qe && !lvl[t]) {
int v = q[qi++];
for (Edge e : adj[v])
if (!lvl[e.to] && e.c >> (30 - L))
q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
}
while (ll p = dfs(s, t, INT_MAX)) flow += p;
} while (lvl[t]);
return flow;
}
bool leftOfMinCut(int a) { return lvl[a] != 0; }
};
template<class T> bool ckmin(T&a, T&b) { bool B = a > b; a = min(a,b); return B; }
template<class T> bool ckmax(T&a, T&b) { bool B = a < b; a = max(a,b); return B; }
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ld,ld> pld;
typedef complex<ld> cd;
typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<vector<int>> vvi;
const ld PI = acos(-1.0);
const ld EPS = 1e-7;
const int MOD = 998244353;
int32_t main() { FAST
int n;
cin >> n;
vector<string> board(n);
F0R(i, n){
cin >> board[i];
}
vector<int> r(n), c(n);
F0R(i, n){
cin >> r[i];
}
F0R(i, n){
cin >> c[i];
}
F0R(i, n){
F0R(j, n){
if (board[i][j] == '-'){
r[i]++;
c[j]++;
}
}
}
int totr = 0;
int totc = 0;
F0R(i, n){
totr += r[i];
totc += c[i];
if (r[i] < 0 || c[i] < 0){
cout << "No\n";
return 0;
}
}
if (totr != totc){
cout << "No\n";
return 0;
}
/*
int so = n + n;
int si = n + n + 1;
Dinic MF(n + n + 2);
F0R(i, n){
MF.addEdge(so, i, r[i]);
MF.addEdge(i + n, si, c[i]);
}
F0R(i, n){
F0R(j, n){
MF.addEdge(i, j + n, 1);
}
}
auto res = MF.calc(so, si);
if (res != totc){
cout << "No\n";
return 0;
}
cout << "Yes\n";
vvi out(n, vi(n));
F0R(i, n){
for(auto e : MF.adj[i]){
if (e.to < so && e.flow()){
out[i][e.to - n] = 1;
}
}
}*/
vvi out(n, vi(n));
F0R(i, n){
vector<pi> rr;
F0R(j, n){
rr.emplace_back(-r[j], j);
}
sort(all(rr));
for (auto [v, j] : rr){
if (c[i] == 0) break;
c[i]--;
if (r[j] == 0) {
cout << "No\n";
return 0;
}
r[j] --;
out[i][j] ++;
}
}
cout << "Yes\n";
F0R(i, n){
F0R(j, n){
if (board[i][j] == '-'){
out[i][j] ^= 1;
}
cout << out[i][j];
}
cout << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3500kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 100 101 101
result:
wrong answer wrong sum at row 2