QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#299562 | #7857. (-1,1)-Sumplete | ucup-team134 | AC ✓ | 1075ms | 129632kb | C++14 | 3.3kb | 2024-01-07 01:26:50 | 2024-01-07 01:26:51 |
Judging History
answer
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
using u128=__uint128_t;
typedef pair<int,int> pii;
const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}
const int maxn=4000+10;
int n,a[maxn][maxn];
pii r[maxn];
int c[maxn],rez[maxn][maxn],orr[maxn],oc[maxn];
int main(){
/// freopen("test.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++){
string s;
cin>>s;
for(int j=0;j<n;j++){
a[i][j+1]=(s[j]=='+')?1:-1;
}
}
for(int i=1;i<=n;i++){
scanf("%d",&r[i].ff);
r[i].ss=i;
orr[i]=r[i].ff;
}
for(int i=1;i<=n;i++){
scanf("%d",&c[i]);
oc[i]=c[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==1){
rez[i][j]=1;
}
else{
r[i].ff++;
c[j]++;
}
}
}
sort(r+1,r+n+1);
int e=1;
int sum=0;
for(int i=1;i<=n;i++){
if(r[i].ff<0 || c[i]<0){
e=0;
break;
}
sum+=r[i].ff-c[i];
}
if(!e || sum!=0){
printf("No\n");
return 0;
}
for(int i=1;i<=n;i++){
vector<pii>pom;
for(int j=1;j<=c[i];j++){
pom.pb(r[n-j+1]);
if(r[n-j+1].ff==0){
e=0;
break;
}
}
if(!e)break;
reverse(pom.begin(),pom.end());
for(int j=0;j<pom.size();j++){
rez[pom[j].ss][i]^=1;
pom[j].ff--;
}
vector<pii>pom2;
int pt1=1;
int pt2=0;
for(int j=1;j<=n;j++){
pii v1,v2;
v1={1e9,-1};
v2={1e9,-1};
if(pt1<=n-c[i])v1=r[pt1];
if(pt2<pom.size())v2=pom[pt2];
if(v1<v2){
///printf("%d %d | %d %d - ",v1.ff,v1.ss,v2.ff,v2.ss);
pom2.pb(v1);
pt1++;
}
else{
///printf("%d %d | %d %d - ",v2.ff,v2.ss,v1.ff,v1.ss);
pom2.pb(v2);
pt2++;
}
}
for(int j=0;j<pom2.size();j++)r[j+1]=pom2[j];
///sort(r+1,r+n+1);
//for(int j=2;j<=n;j++)
// assert(r[j]>=r[j-1]);
/*for(int j=1;j<=n;j++){
printf("%d %d | ",r[j].ff,r[j].ss);
}
printf("\n");*/
}
if(!e){
printf("No\n");
return 0;
}
printf("Yes\n");
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d",(rez[i][j]^1));
if(rez[i][j]==0)oc[j]-=a[i][j];
if(rez[i][j]==0)orr[i]-=a[i][j];
}
printf("\n");
}
int pe=1;
for(int i=1;i<=n;i++){
if(oc[i]!=0 || orr[i]!=0)pe=0;
}
if(pe==0)while(1){}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5772kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 001 001 111
result:
ok n=3
Test #2:
score: 0
Accepted
time: 1ms
memory: 5812kb
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: 5780kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 7780kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 5784kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 0ms
memory: 5900kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 11100101111001101111 01001011011111100100 10100111010000001010 10001111110100101000 11101000101001111011 10110011110101010100 01001100101111111010 11110010010001011000 00000000101100110111 11110001000101101001 00001111111111010111 10100101011111111100 00010110100001001101 10110111001011001001 01...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 2ms
memory: 10164kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 0110000000101101011010111110110111010110000001010010100110100000001101101110100011111110110010110011 0110011010111101000110001110111010001000010000011000011010010010100011110100101011111010101011001111 0010011001110100110000100110000110100000000011001100010111101010111110001101101111101010001101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 20ms
memory: 22432kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 11010101001111100011010101111001111101111001000010011110111011100101001011011101010010001101001001111010001011011011111011000110001000101001101100000000110100101010011110010000011011000100001001100111111001101001100001010010011001011101010000001110010000010100001001111011000000101101110011010001...
result:
ok n=500
Test #9:
score: 0
Accepted
time: 965ms
memory: 129324kb
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...
output:
Yes 10010101011010000111010011111100111010001100011000000011101001101010110100010010001100110111100111010001000110000000010100000100111001110110111010000101001100111001001111001000011100000011101100110110111111011011100000111110110110110111110011011111011100100111010000011001000101000001110100001000...
result:
ok n=4000
Test #10:
score: 0
Accepted
time: 940ms
memory: 129328kb
input:
4000 +---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...
output:
Yes 10001001101001111001111011001100101111111001001000110001000101101011110001010111101011000011000110110101101111101010111010011111000001111100101111001011000101000000001001010100011101111110110000000000011001010010111110100111100001101101000100001100110111011100100001000100110000100100010110101111...
result:
ok n=4000
Test #11:
score: 0
Accepted
time: 1026ms
memory: 129404kb
input:
4000 -+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...
output:
Yes 01001000000100111011000000110000100111000000011010011000000111001000110000101010010110000100010010000101000110010101001010011100110010000110010110011011010001010100100010000011100111011010000001100000110100001000101001000110000011111000110010111111110011111000000001100110111010001100110111100001...
result:
ok n=4000
Test #12:
score: 0
Accepted
time: 957ms
memory: 129364kb
input:
4000 +-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...
output:
Yes 01011111000011010010111110001010010010011000100100011001010111110101101000010001111001100000100100010111110010111011100010001101011101110010001001110110001111000100011101111100110001101010000001101000111011001001100010010101100100000000110001000110100010111000111000010000111001111100110101110110...
result:
ok n=4000
Test #13:
score: 0
Accepted
time: 996ms
memory: 129612kb
input:
4000 -+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...
output:
Yes 01110001000000010111101110110100110000111111000100011011110111011010001000111001010001100111101110100000110011011101010111101011000111000000110011100100000101100101011010110100011110010111111000111000100111011010000001111001101000100100111001001001110011101101110011001100011011011100000011001100...
result:
ok n=4000
Test #14:
score: 0
Accepted
time: 890ms
memory: 129356kb
input:
4000 +--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...
output:
Yes 01100000110011010001001010101011001111110000111000101011011111100101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010100000100110101110010011011010001010000010110010111100010010000101110110100100101010111001001010111100100001111111111100011000010010...
result:
ok n=4000
Test #15:
score: 0
Accepted
time: 1019ms
memory: 129480kb
input:
4000 ---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...
output:
Yes 11100100101011110010000111001010011111010111110010000110100001001111011001001011101110011100011010011101100100111111110101100111110000101100001011010010110100110111010011111110011100000010101110100010110111000111110110010001000000000010001101100011111100011011101001110111111111111010001111010100...
result:
ok n=4000
Test #16:
score: 0
Accepted
time: 980ms
memory: 129396kb
input:
4000 ++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...
output:
Yes 10011000000100110011110001111011011110010000011110010001111001000001111110000001000100000010101000001011100111010101110000011000101000101111101001011001101000001101010001110101001111001110010110101101001110011100000011011111100100110110111011010011000001000100110101110110100110110100110101010110...
result:
ok n=4000
Test #17:
score: 0
Accepted
time: 1000ms
memory: 129632kb
input:
3999 -+-+++---+-----++-++-+++--++-++-----+-++-+---+++-+++-+-+--+++++-++-+++-+---+-----+-++++-+--++-+++--+-++++--+-+-+-+-+----++----+--+---+--+--++-+++--++-+-++--++------+-+--++++--++-+--+----++---+-+---+++++--++-+-++-+++--++---++++-+-+--+-+++++-+-+--+---+---+-+--++++---+-++++-+--++------+++-+++-+-+-...
output:
Yes 10100010101111100110100011001001011101001011100010001011100000010010001011101111101000010110010001101000011010101010110100011101101110110110010101100101001100111111010110000110010110111100101010111000001100101001000110010100001010110100100101011011101110101100001110100001011001111110001000001010...
result:
ok n=3999
Test #18:
score: 0
Accepted
time: 981ms
memory: 129424kb
input:
3998 --------+++--++-++++--+-+-++---+--++---++-+-++--+----++++---+-++-+-++++++++-+-+++---++++++-+--+-------+--+----++--+--+-+--+++---++-+++---+++-++-+++--++-+----+---+--+-++++--++++-++-+-+---+---+-++----+++++++++++--++--+++++-+++++++-+-+--+-+---+++-++-+++++-+-+-+-+++-+-++-+-+--+-+----+++-+-+--++-+--...
output:
Yes 11111110011000110001110000010110001000110100111101110110000111000100001000101000001010101100001111110001001001011100100000110010101001101011001101110110011110100001100110010111010010100001011111011000100010110001100000001110011001011010111001111011000000010110101001010001000110100000100110000010...
result:
ok n=3998
Test #19:
score: 0
Accepted
time: 308ms
memory: 129556kb
input:
4000 ++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...
output:
No
result:
ok n=4000
Test #20:
score: 0
Accepted
time: 344ms
memory: 129376kb
input:
3999 -+-+++---+-----++-++-+++--++-++-----+-++-+---+++-+++-+-+--+++++-++-+++-+---+-----+-++++-+--++-+++--+-++++--+-+-+-+-+----++----+--+---+--+--++-+++--++-+-++--++------+-+--++++--++-+--+----++---+-+---+++++--++-+-++-+++--++---++++-+-+--+-+++++-+-+--+---+---+-+--++++---+-++++-+--++------+++-+++-+-+-...
output:
No
result:
ok n=3999
Test #21:
score: 0
Accepted
time: 252ms
memory: 129292kb
input:
3998 --------+++--++-++++--+-+-++---+--++---++-+-++--+----++++---+-++-+-++++++++-+-+++---++++++-+--+-------+--+----++--+--+-+--+++---++-+++---+++-++-+++--++-+----+---+--+-++++--++++-++-+-+---+---+-++----+++++++++++--++--+++++-+++++++-+-+--+-+---+++-++-+++++-+-+-+-+++-+-++-+-+--+-+----+++-+-+--++-+--...
output:
No
result:
ok n=3998
Test #22:
score: 0
Accepted
time: 1ms
memory: 5732kb
input:
2 +- -- 0 -1 -1 2
output:
No
result:
ok n=2
Test #23:
score: 0
Accepted
time: 1ms
memory: 6052kb
input:
20 --+--------+---++-++ --+++-+----+--++-+++ -+-+-++++---+-+---++ +++-++--++-++-++--++ +---+----+-+++-++++- ----+++++--++----+-+ +-++++----++--++---- ++++++-+-+-++-++--+- -+--+-++++-+-+-+-+-+ --++-+-+--++-++--++- +---+++-+++-+-+-++-+ +++-+--+++-++-+++-+- --++--+-++-+--+-+-++ ----++-+--+-+-++++-+ --+...
output:
No
result:
ok n=20
Test #24:
score: 0
Accepted
time: 217ms
memory: 129436kb
input:
4000 ++---+++-+++-++++++----++-+-+----+-+----+-+-+---+--+-+-----+-+--++++++-++-++++-++----+-++---++++++--+++++--+++--++++-+-+++-++++-+--+++-+++-+--+-+-+++-+-+-+-+++-+-++-++-++++-++-+-++----++++-++++++--+-+---++--+++-++-+-+----+++--+-+--++----+-+++-+-------+++-++--+++-+--+-++----+--------++++--+--+-+...
output:
No
result:
ok n=4000
Test #25:
score: 0
Accepted
time: 903ms
memory: 129336kb
input:
3999 -++--+-+--+++-++--+---++--+---++--+++---++--++---++-+--++---+--++++---+++---++--++-+++++----++-+-+-----++--+++--++--++-+--+-++++-++++--++++-----------+++-+++++++-++--++--+-----++-+-----++++--+++++-+++-+-+--++++-++--++--+--+++-+-+-+-++-++----+---+++++--+++-+---++---+--+-++++-+-++-+-+-+---++-----...
output:
Yes 10011010110001001101110011011100110001110011001110010110011101100001110001110011001000001111001010111110011000110011001011010000100001100001111111111100010000000100110011011111001011111000011000001000101011000010011001101100010101010010011110111000001100010111001110110100001010010101011100111111...
result:
ok n=3999
Test #26:
score: 0
Accepted
time: 895ms
memory: 129336kb
input:
4000 ++---+++-+++-++++++----++-+-+----+-+----+-+-+---+--+-+-----+-+--++++++-++-++++-++----+-++---++++++--+++++--+++--++++-+-+++-++++-+--+++-+++-+--+-+-+++-+-+-+-+++-+-++-++-++++-++-+-++----++++-++++++--+-+---++--+++-++-+-+----+++--+-+--++----+-+++-+-------+++-++--+++-+--+-++----+--------++++--+--+-+...
output:
Yes 00111000100010000001111001010111101011110101011101101011111010110000001001000010011110100111000000110000011000110000101000100001011000100010110101000101010100010100100100001001010011110000100000011010111001100010010101111000110101100111101000101111111000100110001011010011110111111110000110110100...
result:
ok n=4000
Test #27:
score: 0
Accepted
time: 1054ms
memory: 129360kb
input:
3999 -++--+-+--+++-++--+---++--+---++--+++---++--++---++-+--++---+--++++---+++---++--++-+++++----++-+-+-----++--+++--++--++-+--+-++++-++++--++++-----------+++-+++++++-++--++--+-----++-+-----++++--+++++-+++-+-+--++++-++--++--+--+++-+-+-+-++-++----+---+++++--+++-+---++---+--+-++++-+-++-+-+-+---++-----...
output:
Yes 01100101001110110010001100100011001110001100110001101001100010011110001110001100110111110000110101000001100111001100110100101111011110011110000000000011101111111011001100100000110100000111100111110111010100111101100110010011101010101101100001000111110011101000110001001011110101101010100011000000...
result:
ok n=3999
Test #28:
score: 0
Accepted
time: 1075ms
memory: 129460kb
input:
4000 ++---+++-+++-++++++----++-+-+----+-+----+-+-+---+--+-+-----+-+--++++++-++-++++-++----+-++---++++++--+++++--+++--++++-+-+++-++++-+--+++-+++-+--+-+-+++-+-+-+-+++-+-++-++-++++-++-+-++----++++-++++++--+-+---++--+++-++-+-+----+++--+-+--++----+-+++-+-------+++-++--+++-+--+-++----+--------++++--+--+-+...
output:
Yes 11000111011101111110000110101000010100001010100010010100000101001111110110111101100001011000111111001111100111001111010111011110100111011101001010111010101011101011011011110110101100001111011111100101000110011101101010000111001010011000010111010000000111011001110100101100001000000001111001001011...
result:
ok n=4000
Extra Test:
score: 0
Extra Test Passed