Submission #593403

#	Time	Username	Problem	Language	Result	Execution time	Memory
593403		haojiandan	Virus Experiment (JOI19_virus)	C++14	20 / 100	2060 ms	19980 KiB

virus

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
const int INF=1e9;
const int maxn=810;
char s[200010];
int len,n,m,d[maxn][maxn];
int mx[16],dy[300];
int fx[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool vis[maxn][maxn];
int msk[maxn][maxn];
pair<int,int> q[maxn*maxn];
int hd,tl,flag;
vector<pair<int,int> > V;
int calc(int x,int y) {
	int rx=x;
	V.clear(); V.push_back(MP(x,y));
	q[hd=tl=1]=MP(x,y); vis[x][y]=1;
	while (hd<=tl) {
		x=q[hd].first,y=q[hd].second,hd++;
		for (int i=0;i<4;i++) {
			if (flag&&(i&1^1)) continue;
			int a=x+fx[i][0],b=y+fx[i][1];
			if (1<=a&&a<=n&&1<=b&&b<=m&&!vis[a][b]&&d[a][b]) {
				msk[a][b]|=(1<<((i+2)%4));
				if (!flag) V.push_back(MP(a,b));
				if (mx[msk[a][b]]>=d[a][b]) q[++tl]=MP(a,b),vis[a][b]=1;
			}
		}
	}
	if (!flag) { for (pair<int,int> &A : V) msk[A.first][A.second]=vis[A.first][A.second]=0; }
	else { for (int i=1;i<=m;i++) msk[rx][i]=vis[rx][i]=0; }
	return tl;
}
int mn=INF,cnt;
int L[maxn],R[maxn];
void calc2(int x) {
	for (int i=1;i<=m;i++) if (d[x][i]) {
		L[i]=i,R[i]=i;
		while (1) {
			int F=0;
			if (L[i]>1&&d[x][L[i]-1]&&mx[1<<1]>=d[x][L[i]-1]) {
				L[i]--;
				int y=L[i];
				L[i]=min(L[i],L[y]),R[i]=max(R[i],R[y]);
				F=1;
			}
			if (R[i]<m&&d[x][R[i]+1]&&mx[1<<3]>=d[x][R[i]+1]) {
				R[i]++;
				F=1;
			}
			if (!F) break;
		}
		int len=R[i]-L[i]+1;
		if (len<mn) mn=len,cnt=1; else if (mn==len) cnt++;
	}
}
int main() {
	scanf("%d %d %d %s",&len,&n,&m,s+1);
	dy['W']=3,dy['N']=0,dy['E']=1,dy['S']=2;
	int all=0; flag=1;
	for (int i=1;i<=len;i++) s[i+len]=s[i],all|=(1<<dy[s[i]]),flag&=(s[i]=='W'||s[i]=='E');
	for (int t=0;t<16;t++) {
		if ((t&all)==all) { mx[t]=INF; continue; }
		int cnt=0;
		for (int i=1;i<=len*2;i++) {
			if (t>>dy[s[i]]&1) cnt++,mx[t]=max(mx[t],cnt); else cnt=0;
		}
	}
	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) read(d[i][j]);
	if (flag) {
		for (int i=1;i<=n;i++) calc2(i);
	} else {
		for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (d[i][j]) {
			int res=calc(i,j);
			//printf("%d %d\n",i,j);
			if (res<mn) mn=res,cnt=1; else if (res==mn) cnt++;
		}
	}
	printf("%d\n%d\n",mn,cnt);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Compilation message (stderr)

virus.cpp: In function 'int calc(int, int)':
virus.cpp:34:16: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   34 |    if (flag&&(i&1^1)) continue;
      |               ~^~
virus.cpp: In function 'int main()':
virus.cpp:74:56: warning: array subscript has type 'char' [-Wchar-subscripts]
   74 |  for (int i=1;i<=len;i++) s[i+len]=s[i],all|=(1<<dy[s[i]]),flag&=(s[i]=='W'||s[i]=='E');
      |                                                     ~~~^
virus.cpp:79:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   79 |    if (t>>dy[s[i]]&1) cnt++,mx[t]=max(mx[t],cnt); else cnt=0;
      |              ~~~^
virus.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  scanf("%d %d %d %s",&len,&n,&m,s+1);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 0 / 80