QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22574#2841. 赛艇blackswallow#TL 7333ms204908kbC++202.9kb2022-03-09 21:19:452022-04-30 01:22:09

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 01:22:09]
  • 评测
  • 测评结果:TL
  • 用时:7333ms
  • 内存:204908kb
  • [2022-03-09 21:19:45]
  • 提交

answer

//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;

//#define FILE
//#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
#define y1 _y1

const int MAXN = 1510;
const int MAXK = 5e6 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, m, k, Ans;
int sL[MAXN], sR[MAXN];
bitset<MAXN> P[MAXN][MAXN], V[MAXN];
char mmp[MAXN][MAXN], mv[MAXK];
bool tmp[MAXN << 1][MAXN << 1];

template<typename T> inline bool read(T &a) {
	a = 0; char c = getchar(); int f = 1;
	while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
	while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
	return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }

signed main () {
#ifdef FILE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	read(n), read(m), read(k);
	for(int i = 1; i <= n; ++i) {
		scanf("%s", mmp[i] + 1);
		for(int j = 1; j <= m; ++j)
			if(mmp[i][j] == '0') P[i][0].set(j);
		for(int j = 1; j <= m; ++j)
			P[i][j] = P[i][j - 1] >> 1;
	}
	scanf("%s", mv + 1);
	int curx = n, cury = m;
	tmp[curx][cury] = true;
	for(int i = 1; i <= k; ++i) {
		if(mv[i] == 'w') curx--;
		if(mv[i] == 'a') cury--;
		if(mv[i] == 's') curx++;
		if(mv[i] == 'd') cury++;
		tmp[curx][cury] = true;
	}
	int H = 0, mn = INF, len = 0;
	for(int i = 0, sum; i < (MAXN << 1); ++i) {
		sum = 0;
		for(int j = 0; j < (MAXN << 1); ++j)
			sum += tmp[i][j];
		if(!sum) continue;
		++H; sL[H] = -1;
		for(int j = 0; j < (MAXN << 1); ++j) {
			if(!tmp[i][j]) continue;
			if(sL[H] == -1) sL[H] = j;
			sR[H] = j;
		}
	}
	for(int i = 1; i <= H; ++i) mn = min(mn, sL[i]);
	for(int i = 1; i <= H; ++i) {
		sL[i] -= mn, sR[i] -= mn;
		len = max(len, sR[i] + 1);
	}
	for(int i = 0, t = 0, cc = 0; i < (MAXN << 1); ++i) {
		t = 0;
		for(int j = 0; j < (MAXN << 1); ++j) t += tmp[i][j];
		if(!t) continue;
		++cc;
		for(int j = 0; j < (MAXN << 1); ++j) {
			if(!tmp[i][j]) continue;
			V[cc].set(j - mn);
		}
	}
	/*for(int i = 1; i <= H; ++i) {
		for(int j = 0; j < len; ++j)
			cout << V[i][j];
		cout << endl;
	}*/
	for(int i = 1; i + H - 1 <= n; ++i) {
		for(int j = 1; j + len - 1 <= m; ++j) {
			bool flag = true;
			for(int d = 1; d <= H; ++d) {
				if((P[i + d - 1][j] & V[d]) != V[d]) {
					flag = false;
					break;
				}
			}
			Ans += flag;
		}
	}
	printf("%d\n", Ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 9932kb

input:

5 5 5
00000
10000
00000
00000
01001
awdsw

output:

11

result:

ok single line: '11'

Test #2:

score: 0
Accepted
time: 938ms
memory: 63776kb

input:

500 500 50000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

77549

result:

ok single line: '77549'

Test #3:

score: 0
Accepted
time: 331ms
memory: 63580kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #4:

score: 0
Accepted
time: 225ms
memory: 63884kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #5:

score: 0
Accepted
time: 193ms
memory: 64060kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #6:

score: 0
Accepted
time: 210ms
memory: 64404kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #7:

score: 0
Accepted
time: 3869ms
memory: 203892kb

input:

1000 1000 300000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

83496

result:

ok single line: '83496'

Test #8:

score: 0
Accepted
time: 3620ms
memory: 204908kb

input:

1000 1000 1000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

63001

result:

ok single line: '63001'

Test #9:

score: 0
Accepted
time: 7333ms
memory: 203632kb

input:

1000 1000 1500
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

62500

result:

ok single line: '62500'

Test #10:

score: -100
Time Limit Exceeded

input:

1500 1500 5000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:


result: