QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#101563#6377. LaLa and Magic Stonezhoukangyang#WA 3ms7376kbC++173.1kb2023-04-30 11:18:472023-04-30 11:18:49

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-30 11:18:49]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:7376kb
  • [2023-04-30 11:18:47]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long 
#define bs bitset < N >
using namespace std;
const int N = 2007, mod = 998244353;
int n, m;
char s[N][N], S[N][N];
int gen[N], tp;
inline bool canput(int x, int y) {
	if(s[x][y] == '1' || s[x][y + 2] == '1' || s[x + 2][y] == '1' || s[x + 2][y + 2] == '1') 
		return 0;
	if((s[x + 1][y] - '0') + (s[x][y + 1] - '0') + 
		(s[x + 1][y + 2] - '0') + (s[x + 2][y + 1] - '0') > 1) return 0;
	return 1;
}
vector < pair < int, int > > rt[N];
int main() {
//	freopen("data.in", "r", stdin);
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	L(i, 1, n) {
		cin >> (s[i] + 1);
	}
	L(i, 1, n) {
		L(j, 1, m) {
			S[i][j] = s[i][j];
		}
	}
	auto put = [&] (int x, int y) {
		if(x < 1 || x > n || y < 1 || y > m || s[x][y] == '1') {
//			cout<<x <<' '<<y<<endl;
//			cout << "0" << endl;
			exit(0);
		}
		s[x][y] = '1';
		return ;
	};
	int ans = 1;
	L(sum, 2, n + m) {
		for(auto u : rt[sum]) {
			int x1 = u.first, y1 = sum - x1;
			int x2 = u.second, y2 = sum - x2;
			if(s[x1][y1] == '1') {
				put(x2, y2);
			} else if(s[x2][y2] == '1') {
				put(x1, y1);
			} else if(canput(x1, y1)) {
				put(x2, y2);
			} else {
				put(x1, y1);
			}
		}
		tp = 0;
		L(i, 1, n) {
			int j = sum - i;
			if(1 <= j && j <= m && s[i][j] == '0') {
//				cout << i << ", " << j << endl;
				gen[++tp] = i;
				put(i, j);
				put(i, j + 2);
				put(i + 2, j + 2);
				put(i + 2, j);
			}
		}
		L(i, 1, tp) {
			int x = gen[i];
			int y = sum - gen[i];
			if(i < tp && gen[i] + 1 == gen[i + 1]) {
				put(x, y + 1);
				put(x + 1, y);
				put(x + 1, y + 2);
				put(x + 2, y - 1);
				put(x + 2, y + 1);
				put(x + 3, y);
				ans = (ll) ans * 2 % mod;
				++i;
			} else {
				vector < pair < int, int > > VC;
				VC.emplace_back(x, y + 1);
				VC.emplace_back(x + 1, y);
				VC.emplace_back(x + 1, y + 2);
				VC.emplace_back(x + 2, y + 1);
				int ok = 0;
				L(p, 0, 3) {
					if(s[VC[p].first][VC[p].second] == '1') {
						ok = 1;
						L(i, 0, 3) 
							if(i != p) 
								put(VC[i].first, VC[i].second);
//						cout<<"okay put."<<endl;  
						break;
					}
				} 
				if(ok) continue;
				put(x + 1, y);
				put(x, y + 1);
				if(s[x + 1][y + 1] == '0') {
					put(x + 1, y + 1);
					put(x + 2, y + 1);
					put(x + 1, y + 2);
					put(x + 1, y + 3);
					put(x + 2, y + 3);
					put(x + 3, y + 1); 
					put(x + 3, y + 2);
					put(x + 3, y + 3);
					ans = (ll) ans * 2 % mod;
				} else {
					rt[sum + 3].emplace_back(x + 1, x + 2);
				}
			}
		}
//		cout<<endl;
//		L(i, 1, n) {
//			L(j, 1, m) {
//				cout<<s[i][j];
//				S[i][j]=s[i][j];
//			}
//			cout<<endl;
//		}
//		cout<<endl;
	}
	cout << ans << '\n';
	return 0;
}

/*
8 11
11111000111
11111010001
10001000101
00001110001
00001111000
00000000010
11101001000
11101000011
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 4
0001
0000
0000
1000

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3540kb

input:

5 4
0001
0101
0000
1010
1000

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

3 3
111
111
111

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3408kb

input:

3 4
1111
1111
1111

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 2ms
memory: 3420kb

input:

3 1000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 2ms
memory: 3416kb

input:

4 3
111
111
111
111

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 2ms
memory: 3476kb

input:

4 4
1111
1111
1111
1111

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 2ms
memory: 3468kb

input:

4 1000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 2ms
memory: 7328kb

input:

1000 3
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
111
1...

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 2ms
memory: 7376kb

input:

1000 4
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
111...

output:

1

result:

ok 1 number(s): "1"

Test #11:

score: 0
Accepted
time: 1ms
memory: 7328kb

input:

1000 1000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #12:

score: 0
Accepted
time: 2ms
memory: 3472kb

input:

3 3
000
010
010

output:

1

result:

ok 1 number(s): "1"

Test #13:

score: 0
Accepted
time: 2ms
memory: 3460kb

input:

3 3
000
011
000

output:

1

result:

ok 1 number(s): "1"

Test #14:

score: 0
Accepted
time: 2ms
memory: 3468kb

input:

3 3
010
010
000

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 2ms
memory: 3484kb

input:

3 3
000
110
000

output:

1

result:

ok 1 number(s): "1"

Test #16:

score: 0
Accepted
time: 2ms
memory: 3524kb

input:

4 4
1000
0000
0000
0001

output:

2

result:

ok 1 number(s): "2"

Test #17:

score: 0
Accepted
time: 0ms
memory: 3464kb

input:

4 4
0001
0000
0000
1000

output:

2

result:

ok 1 number(s): "2"

Test #18:

score: -100
Wrong Answer
time: 0ms
memory: 3452kb

input:

3 3
010
101
101

output:


result:

wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements