QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21637#2841. 赛艇DaBenZhongXiaSongKuaiDi#AC ✓4759ms26756kbC++202.1kb2022-03-07 17:25:532022-05-08 03:45:30

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 03:45:30]
  • 评测
  • 测评结果:AC
  • 用时:4759ms
  • 内存:26756kb
  • [2022-03-07 17:25:53]
  • 提交

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'