QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#865803#5582. Chocolate Chip FabricationLaVuna47AC ✓257ms40448kbC++202.2kb2025-01-21 23:01:482025-01-21 23:01:48

Judging History

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

  • [2025-01-21 23:01:48]
  • 评测
  • 测评结果:AC
  • 用时:257ms
  • 内存:40448kb
  • [2025-01-21 23:01:48]
  • 提交

answer

//A tree without skin will surely die.
//A man without face is invincible.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, st_, n) for(int i = st_; i < n; ++i)
#define RFOR(i, n, end_) for(int i = (n)-1; i >= end_; --i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif


int solve()
{
	int n, m;
	if(!(cin>>n>>m))return 1;
	vector<string> a(n);
	FOR(i,0,n)cin>>a[i];
	
	auto is_ok=[&](int x, int y) -> bool{
		return x==0 || x==n-1 || y==0 || y==m-1 || a[x-1][y]=='-' || a[x+1][y]=='-' || a[x][y-1]=='-' || a[x][y+1]=='-';
	};
	set<pii> Q;
	FOR(i,0,n)
	{
		FOR(j,0,m)
		{
			if(a[i][j] == 'X' && is_ok(i,j))
			{
				Q.insert({i,j});
			}
		}
	}
	int res=0;
	while(!Q.empty())
	{
		++res;
		set<pii> nxt;
		for(auto [x,y]:Q)
			a[x][y]='-';
		for(auto [x,y]:Q)
		{
			if(x-1>=0 && a[x-1][y]=='X')
				nxt.insert({x-1,y});
			if(x+1<n && a[x+1][y]=='X')
				nxt.insert({x+1,y});
			if(y-1>=0 && a[x][y-1]=='X')
				nxt.insert({x,y-1});
			if(y+1>=0 && a[x][y+1]=='X')
				nxt.insert({x,y+1});
		}
		Q=move(nxt);
	}
	cout<<res<<'\n';
	return 0;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1e9;
    //cin >> TET;
    for (int i = 1; i <= TET; i++)
    {
        if (solve())
        {
            break;
        }
#ifdef ONPC
        cout << "__________________________" << endl;
#endif
    }
#ifdef ONPC
    cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 5
-X-X-
XXXXX
XXXXX
-XXX-
--X--

output:

2

result:

ok single line: '2'

Test #2:

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

input:

4 5
--XXX
--X-X
X-XXX
XX---

output:

1

result:

ok single line: '1'

Test #3:

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

input:

5 5
XXXXX
XXXXX
XXXXX
XXXXX
XXXXX

output:

3

result:

ok single line: '3'

Test #4:

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

input:

9 9
----X----
----X----
----X----
---XXX---
XXXXXXXXX
---XXX---
----X----
----X----
----X----

output:

3

result:

ok single line: '3'

Test #5:

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

input:

7 7
--X-X--
--X-X--
XXXXXXX
--X-X--
XXXXXXX
--X-X--
--X-X--

output:

2

result:

ok single line: '2'

Test #6:

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

input:

3 4
XXXX
-XXX
XXXX

output:

2

result:

ok single line: '2'

Test #7:

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

input:

10 10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

output:

5

result:

ok single line: '5'

Test #8:

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

input:

10 10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXX-XXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

output:

4

result:

ok single line: '4'

Test #9:

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

input:

1 1
X

output:

1

result:

ok single line: '1'

Test #10:

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

input:

3 3
XXX
XX-
XXX

output:

1

result:

ok single line: '1'

Test #11:

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

input:

2 3
XXX
XX-

output:

1

result:

ok single line: '1'

Test #12:

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

input:

3 1
-
-
X

output:

1

result:

ok single line: '1'

Test #13:

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

input:

2 2
XX
-X

output:

1

result:

ok single line: '1'

Test #14:

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

input:

2 2
--
-X

output:

1

result:

ok single line: '1'

Test #15:

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

input:

2 2
XX
XX

output:

1

result:

ok single line: '1'

Test #16:

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

input:

3 5
XXX-X
XXXXX
X-XXX

output:

2

result:

ok single line: '2'

Test #17:

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

input:

4 5
XXXXX
XXX-X
X-XXX
XXXXX

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 90ms
memory: 5632kb

input:

1000 1000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

337

result:

ok single line: '337'

Test #19:

score: 0
Accepted
time: 165ms
memory: 12672kb

input:

1000 1000
-XXX-XXXXXXXXXXXXXXXXXX--XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXX-XXXXXXXXXXX-XXXXXX-XXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXX-XXXXXXXXX-XXXXXXXXXX-XX...

output:

38

result:

ok single line: '38'

Test #20:

score: 0
Accepted
time: 119ms
memory: 26112kb

input:

1000 1000
X--X--XX--X--X---X-XXX---X----X-X-----X-X--X--XX--X----X--X--XX----X-XXX-----X-XXX-X-XX------X-X-X--XXX-X-XX--X-X----XXX-X--XX-X-X-X-XXXXXX-X-----X-X--XXX---X--XXX-X-X-XX----XX-----X-X-XX-X-X--X-X--X-X--X-X----X-X------X--XXXXX---XXXXXX-XX--X-XX-XXXXX-XXXX-X-X--XX---X-X----XXXX-XX---XXX--X...

output:

5

result:

ok single line: '5'

Test #21:

score: 0
Accepted
time: 256ms
memory: 22016kb

input:

999 999
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

15

result:

ok single line: '15'

Test #22:

score: 0
Accepted
time: 250ms
memory: 38528kb

input:

999 999
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

7

result:

ok single line: '7'

Test #23:

score: 0
Accepted
time: 218ms
memory: 40448kb

input:

999 999
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

4

result:

ok single line: '4'

Test #24:

score: 0
Accepted
time: 257ms
memory: 39424kb

input:

999 999
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

2

result:

ok single line: '2'

Test #25:

score: 0
Accepted
time: 12ms
memory: 6912kb

input:

1000 1000
--------------------------------------------------------------------------------------------------------------------X-------X-----------------------------------------------------------------X--------------------------XXX--------------------------------------------------X-------------------...

output:

2

result:

ok single line: '2'

Test #26:

score: 0
Accepted
time: 117ms
memory: 23680kb

input:

1000 1000
XXXX-------------XXX----------XXX--XXX----------X--X----XXXX-XXXXX---------XXXX----------X--------------X-------------X--------X--X-------------X------XXX--X-XXXXXX-XXX------X---------XXX-X-----XXXXXXX--XX----X------X------XXX-------------X-----X----------------XXXXX-XXXXXXX-XXXX-X-X------...

output:

4

result:

ok single line: '4'

Test #27:

score: 0
Accepted
time: 118ms
memory: 14720kb

input:

1000 1000
-----------XXXXXXXXX----XXXXXXX-----------------------------------XXXXXXX-----------------------------------------XXXXXXX-----X-----------XXXXX-XXXXXXXXXXXXXXX------------------XXXXXXXX--XXXXX---------------XXXXXXXXXXXXXX--------XXXXXXXXXXXXXXXX----------------------------XXXXX----XXXXXXX-...

output:

11

result:

ok single line: '11'

Test #28:

score: 0
Accepted
time: 49ms
memory: 5120kb

input:

1000 1000
----------------------------------------------------------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

381

result:

ok single line: '381'

Test #29:

score: 0
Accepted
time: 160ms
memory: 19072kb

input:

1000 1000
----------X--XXXXXXXXXXXXXXX------XXXXXXXXXXXXXXXXXXXX----------------XXX--XXX--X------XXXX-X------------------XXXXXXX-----------XXX--X----------XXX--------------------XXXXX-----------------------X---X---------XXXXX-----------XXXXXXXXXXXXXXX--------XXXXXXXXX----------XXXXXXX---------------...

output:

10

result:

ok single line: '10'

Test #30:

score: 0
Accepted
time: 153ms
memory: 5508kb

input:

1000 1000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--------------XXXXXXXXXXX----------------------------------------------------------------------------------------------------------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

155

result:

ok single line: '155'

Test #31:

score: 0
Accepted
time: 41ms
memory: 4992kb

input:

999 999
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...

output:

499

result:

ok single line: '499'

Test #32:

score: 0
Accepted
time: 113ms
memory: 27776kb

input:

999 999
X-XXX-XXX-XXX-X-X-XXX-X-XXXXXXX-XXX-XXXXXXX-XXX-XXXXXXX-X-XXXXX-XXX-X-XXXXXXX-XXXXX-X-XXX-XXX-XXXXX-XXXXXXXXX-X-X-XXXXXXX-XXX-XXXXXXXXX-XXX-XXXXXXXXXXX-XXX-X-XXXXXXXXX-X-XXX-XXX-XXXXXXXXXXXXXXX-XXX-XXX-X-X-X-XXXXXXXXX-XXX-X-XXXXX-XXX-X-XXXXX-XXXXXXX-XXXXXXX-XXXXXXX-XXX-X-XXX-XXXXXXXXXXX-X-X-...

output:

2

result:

ok single line: '2'

Test #33:

score: 0
Accepted
time: 116ms
memory: 28032kb

input:

999 999
XXXXX-XXXXX-X-X-X-XXXXXXXXXXX-XXX-XXX-X-XXXXXXX-X-XXXXX-XXXXXXXXX-XXXXXXX-XXX-X-X-XXX-X-XXX-XXXXX-XXX-X-X-XXX-XXX-X-XXX-XXXXXXX-XXXXX-XXXXXXXXX-XXX-XXXXXXXXXXXXXXX-XXX-X-X-XXXXX-X-X-XXXXX-XXXXX-XXXXXXXXXXXXX-XXXXXXX-XXX-XXX-XXX-X-X-XXXXXXX-XXXXXXX-XXXXXXX-XXXXX-X-XXXXXXX-X-X-XXX-XXXXXXXXX-X-...

output:

2

result:

ok single line: '2'

Test #34:

score: 0
Accepted
time: 248ms
memory: 34944kb

input:

1000 1000
XXXXX-XX-XXX-X-XXX-XXXXXXXXXXXXXXXXX-XXXXXX-XXXXXXXXXXXXX-XXXXXXX-XXXXXXXXXXXXXXX-XXXXXX-XX-XXXXXXXXXXXXXXXXXX-XXXXXX-XXXXXXXXXXX-XXXXXXXXXXXXXXXXX-X-XXXXXX-XXXXXXXXXXXXXXXXXXXXXX-XXXXXXX-XX-XXXX-XXXXXXXXXXXXXXXX-XXX-XXXXX-XXX-XXXX-XXXXXXXXXXXXXXXXXXXXXXXX-XXXXX-XXX-XXXXXX-XXX-XXXXXXXXXXXX...

output:

8

result:

ok single line: '8'

Test #35:

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

input:

1000 1000
X-XXX-XX-XXX-XXXXX-X---X-XXXXXXXXX--XX----X--X--X-X---X-XX--XXXXXX--XXXXX-XX--XXX---X-----X---XX---X--XXXXX-----XX--XX-X-----X-X-X-XX----XX-XXXX--X-X--X------XXXXXXX-XX-X--XX-----XXX-XX--XXX-X--X--X-X-XXX---X-XX---X--XX-X-X-X--XX-X-X-X-XXXX-XXXX--X-X-XXX-X-----XXX--XX--X--X-X-XXXXXX-X-X-XX...

output:

3

result:

ok single line: '3'

Test #36:

score: 0
Accepted
time: 23ms
memory: 9472kb

input:

1000 1000
X---X------------X--X-----X----------X-----------------------------------------------------------X--X---X---X-------X---X-----------------------XX-----------------X-----X----XX---------------------------X------XX---------X-----------------X--------X--------------X---X-----X----------------...

output:

2

result:

ok single line: '2'

Test #37:

score: 0
Accepted
time: 64ms
memory: 5248kb

input:

1000 1000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

500

result:

ok single line: '500'