QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#22576#2841. 赛艇blackswallow#TL 10026ms294744kbC++204.1kb2022-03-09 21:42:592022-04-30 01:23:15

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:23:15]
  • 评测
  • 测评结果:TL
  • 用时:10026ms
  • 内存:294744kb
  • [2022-03-09 21:42:59]
  • 提交

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, blen;
int sL[MAXN], sR[MAXN], sum[MAXN][MAXN];
//bitset<MAXN> P[MAXN][MAXN], V[MAXN];
char mmp[MAXN][MAXN], mv[MAXK];
bool tmp[MAXN << 1][MAXN << 1];

struct BS {
	ull B[30];
	void clear() { memset(B, 0, sizeof B); }
	BS shift() {
		static BS res; res.clear();
		for(int i = 0; i < blen; ++i) {
			if(i) res.B[i - 1] |= ((B[i] & 1ll) << 63);
			res.B[i] = B[i] >> 1;
		}
		return res;
	}
	BS operator & (const BS &b) const {
		static BS res; res.clear();
		for(int i = 0; i < blen; ++i)
			res.B[i] = B[i] & b.B[i];
		return res;
	}
	bool operator == (const BS &b) const {
		for(int i = 0; i < blen; ++i)
			if(B[i] != b.B[i]) return false;
		return true;
	}
	void set(int x) { B[x >> 6] |= (1ll << (x & 63)); }
} V[MAXN], P[MAXN][MAXN];

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...); }

int S(int a, int b, int c, int d) {
	return sum[b][d] - sum[a - 1][d] - sum[b][c - 1] + sum[a - 1][c - 1];
}

signed main () {
#ifdef FILE
	freopen("B.in", "r", stdin);
	freopen("B.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) sum[i][j] = mmp[i][j] - '0';
	}
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 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);
	}
	while(blen * 64 < len) blen++;
	//cerr << len << ' ' << H << ' ' << blen << endl;
	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 <= n; ++i) {
		for(int j = 1; j < len; ++j)
			if(mmp[i][j] == '0') P[i][0].set(j);
		for(int j = 1; j <= m - len + 1; ++j) {
			P[i][j] = P[i][j - 1].shift();
			if(mmp[i][len + j - 1] == '0') P[i][j].set(len - 1);
		}
	}
	for(int i = 1; i + H - 1 <= n; ++i) {
		for(int j = 1; j + len - 1 <= m; ++j) {
			bool flag = true;
			if(S(i, i + H - 1, j, j + len - 1) == 0) { ++Ans; continue; }
			for(int d = 1; d <= H; ++d) {
				if(!S(i + d - 1, i + d - 1, j, j + len - 1)) continue;
				if((P[i + d - 1][j] & V[d]) == V[d]) continue;
				flag = false; break;
			}
			Ans += flag;
		}
	}
	printf("%d\n", Ans);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 14072kb

input:

5 5 5
00000
10000
00000
00000
01001
awdsw

output:

11

result:

ok single line: '11'

Test #2:

score: 0
Accepted
time: 21ms
memory: 53992kb

input:

500 500 50000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

77549

result:

ok single line: '77549'

Test #3:

score: 0
Accepted
time: 206ms
memory: 52588kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #4:

score: 0
Accepted
time: 127ms
memory: 52932kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #5:

score: 0
Accepted
time: 123ms
memory: 52872kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #6:

score: 0
Accepted
time: 135ms
memory: 52456kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #7:

score: 0
Accepted
time: 2262ms
memory: 159548kb

input:

1000 1000 300000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

83496

result:

ok single line: '83496'

Test #8:

score: 0
Accepted
time: 2366ms
memory: 143928kb

input:

1000 1000 1000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

63001

result:

ok single line: '63001'

Test #9:

score: 0
Accepted
time: 3880ms
memory: 142892kb

input:

1000 1000 1500
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

62500

result:

ok single line: '62500'

Test #10:

score: 0
Accepted
time: 8629ms
memory: 293556kb

input:

1500 1500 5000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

141376

result:

ok single line: '141376'

Test #11:

score: 0
Accepted
time: 1047ms
memory: 294744kb

input:

1500 1500 5000000
100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110...

output:

22801

result:

ok single line: '22801'

Test #12:

score: 0
Accepted
time: 5ms
memory: 14072kb

input:

2 2 4
00
01
dada

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 10026ms
memory: 293724kb

input:

1500 1500 5000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

141376

result:

ok single line: '141376'

Test #14:

score: -100
Time Limit Exceeded

input:

1500 1500 2250
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:


result: