#include<bits/stdc++.h>
#define F first
#define S second
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
using namespace std;
string tb(ll x)
{
string s = "";
while(x>0)
{
if(x&1)
s+='1';
else
s+='0';
x/=2;
}
while(s.size()<4)
s+='0';
return s;
}
int main()
{
d3
int m;
int16_t r,c;
string d;
cin >> m >> r >> c;
cin >> d;
int a[r+1][c+1];
int b[2][2][2][2];
for(int16_t i = 1 ; r>=i ; i++)
for(int16_t j = 1 ; c>=j ; j++)
{
cin >> a[i][j];
if(a[i][j]==0)
a[i][j]=1e5+1;
}
d+=d;
for(int8_t i = 1 ; 16>=i ; i++)
{
string s = tb(i);
bool l1 = 0 , l2 = 0 , l3 = 0 , l4 = 0;
if(s[0]=='1')
l1=1;
if(s[1]=='1')
l2=1;
if(s[2]=='1')
l3=1;
if(s[3]=='1')
l4=1;
int lon = 0;
int cur = 0;
for(int j = 0 ; d.size()>j ; j++)
{
if((d[j]=='S'&&l1)||(d[j]=='N'&&l2)||(d[j]=='E'&&l3)||(d[j]=='W'&&l4))
{
cur++;
continue;
}
lon=max(lon,cur);
cur=0;
}
lon=max(lon,cur);
if(lon==2*m)
lon=1e5;
b[l1][l2][l3][l4]=lon;
}
int mn = 1e6;
int ans = 0;
pair<int,int> A[r*c];
for(int i = 1 ; r>=i ; i++)
{
for(int j = 1 ; c>=j ; j++)
{
A[(i-1)*c+j-1]={i,j};
}
}
random_shuffle(A,A+r*c);
bool infected[r+2][c+2];
bool tak[r+1][c+1];
memset(tak,0,sizeof(tak));
memset(infected,0,sizeof(infected));
for(int iiii = 0 ; r*c>iiii ; iiii++)
{
int16_t x = A[iiii].F;
int16_t y = A[iiii].S;
if(a[x][y]>1e5)
continue;
vector<pair<int,int>> qwerty;
queue<pair<int16_t,int16_t>> q;
q.push({x,y});
bool ge = 0;
int mn1 = 0;
while(!q.empty())
{
pair<int16_t,int16_t> nod = q.front();
q.pop();
if(infected[nod.F][nod.S])
continue;
qwerty.pb({nod.F,nod.S});
infected[nod.F][nod.S]=1;
mn1++;
if(mn1>mn)
break;
for(int8_t ii = 0 ; 4>ii ; ii++)
{
int16_t xx = nod.F , yy = nod.S;
if(ii==1)
xx++;
else if(ii==2)
xx--;
else if(ii==3)
yy++;
else
yy--;
if(xx<1||xx>r||yy<1||yy>c||infected[xx][yy])
continue;
bool l1 = 0 , l2 = 0 , l3 = 0 , l4 = 0;
if(infected[xx+1][yy])
l1=1;
if(infected[xx-1][yy])
l2=1;
if(infected[xx][yy+1])
l3=1;
if(infected[xx][yy-1])
l4=1;
if(b[l1][l2][l3][l4]>=a[xx][yy])
{
if(tak[xx][yy])
{
ge=1;
break;
}
q.push({xx,yy});
}
}
if(ge)
break;
}
tak[x][y]=1;
for(auto it : qwerty)
infected[it.F][it.S]=0;
if(ge)
continue;
if(mn1==mn)
ans++;
if(mn1<mn)
{
ans=1;
mn=mn1;
}
}
cout << mn << "\n" << ans*mn;
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:58:33: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
58 | for(int j = 0 ; d.size()>j ; j++)
| ~~~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
98 ms |
8992 KB |
Output is correct |
3 |
Correct |
117 ms |
9216 KB |
Output is correct |
4 |
Correct |
100 ms |
9220 KB |
Output is correct |
5 |
Correct |
107 ms |
9044 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
192 ms |
9424 KB |
Output is correct |
8 |
Correct |
62 ms |
4088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
6 ms |
860 KB |
Output is correct |
3 |
Correct |
21 ms |
856 KB |
Output is correct |
4 |
Correct |
7 ms |
860 KB |
Output is correct |
5 |
Correct |
21 ms |
856 KB |
Output is correct |
6 |
Correct |
22 ms |
860 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
19 ms |
860 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
3 ms |
860 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
18 ms |
856 KB |
Output is correct |
14 |
Correct |
20 ms |
860 KB |
Output is correct |
15 |
Correct |
20 ms |
860 KB |
Output is correct |
16 |
Correct |
19 ms |
860 KB |
Output is correct |
17 |
Correct |
11 ms |
856 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
21 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
98 ms |
8992 KB |
Output is correct |
3 |
Correct |
117 ms |
9216 KB |
Output is correct |
4 |
Correct |
100 ms |
9220 KB |
Output is correct |
5 |
Correct |
107 ms |
9044 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
192 ms |
9424 KB |
Output is correct |
8 |
Correct |
62 ms |
4088 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
6 ms |
860 KB |
Output is correct |
11 |
Correct |
21 ms |
856 KB |
Output is correct |
12 |
Correct |
7 ms |
860 KB |
Output is correct |
13 |
Correct |
21 ms |
856 KB |
Output is correct |
14 |
Correct |
22 ms |
860 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
19 ms |
860 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
3 ms |
860 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
18 ms |
856 KB |
Output is correct |
22 |
Correct |
20 ms |
860 KB |
Output is correct |
23 |
Correct |
20 ms |
860 KB |
Output is correct |
24 |
Correct |
19 ms |
860 KB |
Output is correct |
25 |
Correct |
11 ms |
856 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
21 ms |
860 KB |
Output is correct |
28 |
Correct |
317 ms |
18528 KB |
Output is correct |
29 |
Correct |
343 ms |
19552 KB |
Output is correct |
30 |
Correct |
260 ms |
12732 KB |
Output is correct |
31 |
Correct |
150 ms |
9068 KB |
Output is correct |
32 |
Correct |
160 ms |
10192 KB |
Output is correct |
33 |
Correct |
94 ms |
9044 KB |
Output is correct |
34 |
Correct |
319 ms |
21892 KB |
Output is correct |
35 |
Correct |
265 ms |
15052 KB |
Output is correct |
36 |
Correct |
216 ms |
9044 KB |
Output is correct |
37 |
Correct |
342 ms |
13036 KB |
Output is correct |
38 |
Correct |
382 ms |
18424 KB |
Output is correct |
39 |
Correct |
147 ms |
9304 KB |
Output is correct |
40 |
Correct |
167 ms |
9460 KB |
Output is correct |
41 |
Correct |
100 ms |
9196 KB |
Output is correct |
42 |
Correct |
182 ms |
16980 KB |
Output is correct |
43 |
Correct |
201 ms |
17660 KB |
Output is correct |
44 |
Correct |
49 ms |
4084 KB |
Output is correct |