QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#305520 | #7857. (-1,1)-Sumplete | qiling | WA | 1ms | 3644kb | C++14 | 2.6kb | 2024-01-15 15:16:07 | 2024-01-15 15:16:07 |
Judging History
answer
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#define endl '\n'
#define N 4010
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> sz(n + 1, 0);
vector<vector<int> > mp(n + 1, vector<int> (n + 1, 0));
for (int i = 1; i <= n; ++ i) {
string s;
cin >> s;
for (int j = 0; j < s.length(); ++ j) {
if(s[j] == '+') {
++ sz[i];
mp[i][j + 1] = 1;
}else mp[i][j + 1] = -1;
}
}
vector<vector<int> > sum(2, vector<int>(n + 1));
for (int i = 0; i < 2; ++ i) {
for (int j = 1; j <= n; ++ j) {
cin >> sum[i][j];
}
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
if(mp[j][i] == -1) ++ sum[1][i];
if(mp[i][j] == -1) ++ sum[0][i];
}
}
int sum1 = 0, sum2 = 0;
for (int i = 1; i <= n; ++ i) {
if(sum[0][i] > n || sum[1][i] > n || sum[0][i] < 0 || sum[1][i] < 0) {
cout << "No" << endl;
return 0;
}
sum1 += sum[0][i];
sum2 += sum[1][i];
}
if(sum1 != sum2) {
cout << "No" << endl;
return 0;
}
int cnt = 0;
for (int i = 1; i <= n; ++ i) {
if(sum[1][i] > 0) ++ cnt;
}
vector<vector<int> > ans(n + 1, vector<int> (n + 1, 0));
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
if(mp[i][j] == -1) ans[i][j] = 1;
else ans[i][j] = 0;
}
}
for (int i = 1; i <= n; ++ i) {
if(sum[0][i] > cnt) {
cout << "No" << endl;
return 0;
}
vector<int> buk[N];
for (int j = 1; j <= n; ++ j) {
buk[sum[1][j]].push_back(j);
}
for (int j = n, c = sum[0][i]; j >= 1 && c; -- j) {
if(buk[j].size()) {
for (int k = 0; k < min(c, (int)buk[j].size()); ++ k) {
if(mp[i][buk[j][k]] == 1) ans[i][buk[j][k]] = 1;
else ans[i][buk[j][k]] = 0;
if(-- sum[1][buk[j][k]] == 0) -- cnt;
}
c -= buk[i].size();
}
}
}
cout << "Yes" << endl;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
cout << ans[i][j];
}
cout << endl;
}
return 0;
}
/*
3
+-+
-++
+-+
1 1 1
1 -1 3
3
---
-++
+++
-2 -1 0
-2 -1 0
3
+-+
-++
++-
1 0 2
2 2 -1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3572kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 111 001 001
result:
ok n=3
Test #2:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
3 --- -++ +++ -2 -1 0 -2 -1 0
output:
Yes 110 100 000
result:
ok n=3
Test #3:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3552kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
No
result:
wrong answer Jury has the answer but participant has not