QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#510118 | #1978. Stabbing Number | PetroTarnavskyi# | AC ✓ | 0ms | 3824kb | C++20 | 2.0kb | 2024-08-08 21:17:07 | 2024-08-08 21:17:18 |
Judging History
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;
}
详细
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'