QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#510118#1978. Stabbing NumberPetroTarnavskyi#AC ✓0ms3824kbC++202.0kb2024-08-08 21:17:072024-08-08 21:17:18

Judging History

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

  • [2024-08-08 21:17:18]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3824kb
  • [2024-08-08 21:17:07]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	vector<string> v(n);
	FOR (i, 0, n)
		cin >> v[i];
	
	VI mx(m, -1), mn(m, 74);
	FOR (i, 0, n)
	{
		FOR (j, 0, m)
		{
			if (v[i][j] == '*')
			{
				mx[j] = max(mx[j], i);
				mn[j] = min(mn[j], i);
			}
		}
	}
	VI a;
	FOR (i, 0, m)
	{
		if (mx[i] == -1) continue;
		if (a.empty() || a.back() != mx[i] - mn[i])
			a.PB(mx[i] - mn[i]);
	}
	
	FOR (i, 0, SZ(a))
		cerr << a[i] << ' ';
	cerr << '\n';
	if (SZ(a) == 1)
	{
		cout << 1 << '\n';
		return 0;
	}
	if (SZ(a) <= 5)
	{
		cout << 2 << '\n';
		return 0;
	}	
	FOR (t, 0, 2)
	{
		FOR(i, 1, SZ(a))
		{
			int hL = a[i - 1];
			int hR = a[i];
			FOR(j, 0, SZ(a))
			{
				if(j < i)
					hL = min(hL, a[j]);
				else
					hR = min(hR, a[j]);
			}
			if(hL > hR || a[i - 1] > hR)
				continue;
			bool ok = 1;
			int last = -1;
			FOR(j, 0, i)
			{
				if(a[j] == hL)
				{
					ok &= (j - last - 1 <= 2);
					last = j;
				}
			}
			FOR(j, last + 1, i)
				ok &= a[j] == a[i - 1];
			
			last = SZ(a);
			RFOR(j, SZ(a), i)
			{
				if(a[j] == hR)
				{
					ok &= (last - j - 1 <= 2);
					last = j;
				}
			}
			ok &= (last - (i - 1) - 1 <= 2);
			
			
			if(ok)
			{
				cout << "2\n";
				return 0;
			}
		}
		reverse(ALL(a));
	}
	int hR = *min_element(ALL(a));
	int last = SZ(a);
	bool ok = 1;
	RFOR(j, SZ(a), 0)
	{
		if(a[j] == hR)
		{
			ok &= (last - j - 1 <= 2);
			last = j;
		}
	}
	ok &= (last - (0 - 1) - 1 <= 2);
	
	if(ok)
		cout << "2\n";
	else
		cout << "3\n";
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

10 13
.....****....
.....*..*....
.....*..***..
.....*....*..
.....*....***
...***......*
...*........*
****........*
*...........*
*************

output:

2

result:

ok single line: '2'

Test #2:

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

input:

8 15
...............
.........*****.
....***..*...*.
....*.*..*...*.
.****.****...*.
.*...........*.
.*************.
...............

output:

2

result:

ok single line: '2'

Test #3:

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

input:

16 25
...............**********
...............*........*
............****........*
............*...........*
..........***...........*
..........*.............*
........***.............*
........*...............*
.....****...............*
.....*..................*
.....*..................*
...***.....

output:

3

result:

ok single line: '3'

Test #4:

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

input:

13 25
........******...........
........*....*...........
.....****....*...........
.....*.......****........
.....*..........*........
.....*..........****.....
.....*.............*.....
.....*.............******
...***..................*
...*....................*
****....................*
*..........

output:

3

result:

ok single line: '3'

Test #5:

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

input:

13 25
........******...........
........*....*...........
.....****....****........
.....*..........*........
.....*..........*........
.....*..........*........
.....*..........*........
.....*..........*........
...***..........*****....
...*................*....
****................*****
*..........

output:

3

result:

ok single line: '3'

Test #6:

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

input:

8 24
.........****....*******
...****..*..*....*.....*
...*..*..*..*..***.....*
****..*..*..*..*.......*
*.....****..*..*.......*
*...........****.......*
*......................*
************************

output:

2

result:

ok single line: '2'

Test #7:

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

input:

10 24
...............****.....
.........****..*..*.....
...****..*..*..*..*.....
...*..*..*..*..*..*.....
****..*..*..*..*..*.....
*.....****..*..*..*.....
*...........****..*.....
*.................******
*......................*
************************

output:

3

result:

ok single line: '3'

Test #8:

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

input:

14 25
........******...........
........*....*...........
.....****....*...........
.....*.......*...........
.....*.......*****.......
.....*...........*.......
...***...........*.......
...*.............*.......
...*.............****....
...*................*....
****................*....
*..........

output:

3

result:

ok single line: '3'

Test #9:

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

input:

20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
.**************.....
.*............*.....
.*............*.....
.*............*.....
.**************.....
...

output:

1

result:

ok single line: '1'

Test #10:

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

input:

20 20
....................
....................
....................
....................
......*********.....
......*.......*.....
......*.......*.....
......*.......*.....
......*.......*.....
......*.......*.....
......*.......*.....
......*.......*.....
......*.......*.....
......*.......******
...

output:

2

result:

ok single line: '2'

Test #11:

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

input:

20 20
....................
....................
....................
......****..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
...

output:

2

result:

ok single line: '2'

Test #12:

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

input:

20 20
....................
....................
....................
.****...............
.*..*...............
.*..*.......*****...
.*..*.......*...*...
.*..*****...*...*...
.*......*...*...*...
.*......*...*...*...
.*......*...*...*...
.*......*...*...*...
.*......*...*...*...
.*......*...*...*...
...

output:

2

result:

ok single line: '2'

Test #13:

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

input:

40 40
........................................
..............******....................
..............*....*....................
..............*....*....................
..............*....*....................
..............*....*....................
..............*....*....................
..........

output:

2

result:

ok single line: '2'

Test #14:

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

input:

40 40
..........*****.........................
..........*...*.........................
..........*...*.........................
..........*...*.........................
......*****...*.........................
......*.......*.........................
......*.......*.........******..........
......*...

output:

2

result:

ok single line: '2'

Test #15:

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

input:

40 40
.................*****..................
.................*...*.......***........
.................*...*.......*.*........
.................*...*.......*.*........
.................*...*.......*.*........
.................*...*.......*.*........
.................*...*.......*.*........
..........

output:

3

result:

ok single line: '3'

Test #16:

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

input:

40 40
...............******...................
...............*....*...................
...............*....*...................
...............*....*...................
...............*....*...................
...............*....*...................
...............*....*...................
..........

output:

2

result:

ok single line: '2'

Test #17:

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

input:

40 40
.....................****...............
.....................*..*.***...........
.............***.....*..*.*.*...........
.............*.*.....*..*.*.*...........
.............*.*.....*..*.*.*...........
.............*.*.***.*..*.*.*...........
.............*.*.*.*.*..*.*.*...........
..........

output:

3

result:

ok single line: '3'

Test #18:

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

input:

40 40
........................................
........................................
........................................
........................................
........................................
........................................
........................................
..........

output:

3

result:

ok single line: '3'