QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21637 | #2841. 赛艇 | DaBenZhongXiaSongKuaiDi# | AC ✓ | 4759ms | 26756kb | C++20 | 2.1kb | 2022-03-07 17:25:53 | 2022-05-08 03:45:30 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
#pragma GCC optimize(3)
using namespace std;
const int N=1505,M=5000005;
int n,m,k;
int rx,ry,mnr[N],mxr[N];
char mpa[N][N],mpb[N][N],s[M];
ull a[N][N],b[N][N];
// 2^6=64
inline void Adda(ull i,ull j){a[i][j>>6]^=(1ull<<(j&63));}
inline void Addb(ull i,ull j){b[i][j>>6]^=(1ull<<(j&63));}
inline ull range(ull i,ull p,ull q){return ((a[i][p>>6]>>(p&63))&((1ull<<(q-p+1))-1ull));}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
scanf("%s",mpa[i]);
Adda(i,0),Adda(i,m+1);
for(int j=0;j<m;j++){
if(mpa[i][j]=='1') Adda(i,j+1);
}
}
scanf("%s",s);
int x=0,y=0,mnx=0,mxx=0,mny=0,mxy=0;
for(int i=0;i<k;i++){
if(s[i]=='w') x--;else if(s[i]=='s') x++;else if(s[i]=='a') y--;else if(s[i]=='d') y++;
if(x<mnx) mnx=x;if(x>mxx) mxx=x;if(y<mny) mny=y;if(y>mxy) mxy=y;
}
rx=mxx-mnx+1,ry=mxy-mny+1;
//cout<<rx<<" "<<ry<<endl;
x=-mnx,y=-mny;mpb[x][y]='1';
for(int i=0;i<k;i++){
if(s[i]=='w') x--;else if(s[i]=='s') x++;else if(s[i]=='a') y--;else if(s[i]=='d') y++;
mpb[x][y]='1';
}
for(int i=0;i<rx;i++){
mnr[i]=(1ull<<30),mxr[i]=-mnr[i];
for(int j=0;j<ry;j++){
if(mpb[i][j]=='1'){
Addb(i,j);
if(j<mnr[i]) mnr[i]=j;
mxr[i]=j;
}
}
}
//for(int i=0;i<=n;i++) {for(int j=0;j<=m;j++) cout<<a[i][j]<<" ";
//cout<<endl;}
int ans=0;
for(int i=1;i<=n-rx+1;i++){
for(int j=1;j<=m-ry+1;j++){
bool OK=true;
for(int l=0;l<rx;l++){
int now=j,bu=(1<<6)-(now&63),kuai=(((now>>6)+1)<<6);
for(int ll=0;ll<=(mxr[l]>>6);ll++,now+=(1<<6),kuai+=(1<<6)){
if(b[l][ll]){
if(now&63){
if( ( range(l+i,now,kuai-1) | (range(l+i,kuai,now+(1<<6)-1)<<bu) ) & b[l][ll]){
//cout<<i<<" "<<j<<" false!"<<endl;
OK=false;
goto ending_;
}
}
else{
if(a[l+i][now>>6] & b[l][ll]){
//cout<<i<<" "<<j<<" false!"<<endl;
OK=false;
goto ending_;
}
}
}
}
}
ending_: if(OK) ans++;
}
}
cout<<ans<<endl;
}
/*
5 6 5
000000
001001
000100
001000
000001
dwdaa
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11844kb
input:
5 5 5 00000 10000 00000 00000 01001 awdsw
output:
11
result:
ok single line: '11'
Test #2:
score: 0
Accepted
time: 179ms
memory: 13116kb
input:
500 500 50000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
77549
result:
ok single line: '77549'
Test #3:
score: 0
Accepted
time: 79ms
memory: 13304kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #4:
score: 0
Accepted
time: 28ms
memory: 13244kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #5:
score: 0
Accepted
time: 42ms
memory: 14336kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #6:
score: 0
Accepted
time: 28ms
memory: 13816kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #7:
score: 0
Accepted
time: 605ms
memory: 17152kb
input:
1000 1000 300000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
83496
result:
ok single line: '83496'
Test #8:
score: 0
Accepted
time: 748ms
memory: 18416kb
input:
1000 1000 1000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
63001
result:
ok single line: '63001'
Test #9:
score: 0
Accepted
time: 737ms
memory: 17956kb
input:
1000 1000 1500 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
62500
result:
ok single line: '62500'
Test #10:
score: 0
Accepted
time: 4759ms
memory: 26756kb
input:
1500 1500 5000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
141376
result:
ok single line: '141376'
Test #11:
score: 0
Accepted
time: 857ms
memory: 25476kb
input:
1500 1500 5000000 100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110...
output:
22801
result:
ok single line: '22801'
Test #12:
score: 0
Accepted
time: 3ms
memory: 11880kb
input:
2 2 4 00 01 dada
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 4635ms
memory: 25652kb
input:
1500 1500 5000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
141376
result:
ok single line: '141376'
Test #14:
score: 0
Accepted
time: 4231ms
memory: 20876kb
input:
1500 1500 2250 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
140625
result:
ok single line: '140625'
Test #15:
score: 0
Accepted
time: 5ms
memory: 12032kb
input:
50 60 20 000000000000000000000000010000000000000000000010000000000000 000000000000000000000000000000000000000000000000010000000000 000000000000000000000000000000000000000000010000000000001000 000000000000000000000000000000000100000000000000010000000000 00000000010000000000000000000000000000000000000...
output:
1633
result:
ok single line: '1633'
Test #16:
score: 0
Accepted
time: 2ms
memory: 11876kb
input:
60 50 500 00000000000000000000001000000000000000000100000000 00000000000000000000000010000000001000000000000000 00000000000000000000000000000000000000000000100000 00000000000000000000000000001000000000000010000000 00000000010000000000000000000000000000000000000000 00000000000000000000000000000000000...
output:
3
result:
ok single line: '3'
Test #17:
score: 0
Accepted
time: 70ms
memory: 14028kb
input:
500 500 500000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15876
result:
ok single line: '15876'
Test #18:
score: 0
Accepted
time: 30ms
memory: 12260kb
input:
500 500 500 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
228475
result:
ok single line: '228475'
Test #19:
score: 0
Accepted
time: 31ms
memory: 12164kb
input:
500 500 1000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
53530
result:
ok single line: '53530'
Test #20:
score: 0
Accepted
time: 14ms
memory: 14228kb
input:
500 500 50000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
2
result:
ok single line: '2'
Test #21:
score: 0
Accepted
time: 75ms
memory: 13232kb
input:
500 500 100000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
9699
result:
ok single line: '9699'