Submission #297161

#	Time	Username	Problem	Language	Result	Execution time	Memory
297161		Bill_00	Linear Garden (IOI08_linear_garden)	C++14	0 / 100	264 ms	65540 KiB

linear_garden

#include <bits/stdc++.h>
#define pb push_back
#define pp push
#define ff first
#define ss second
#define ll long long
#define mp make_pair
using namespace std;
char s[1000000];
unordered_map<long long,unordered_map<long long,unordered_map<long long,long long> > >u;
int main(){
	long long n,m;
	scanf("%lld%lld",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%c",&s[i]);
	}
	u[0][0][0]=1;
	for(int i=1;i<=n;i++){
		int o=0;
		u[i][2][0]=(u[i-1][1][0]+u[i-1][1][-1])%m;
		u[i][2][-1]=u[i-1][1][-2];
		u[i][1][0]=(u[i-1][0][0]+u[i-1][0][-1])%m;
		u[i][1][-1]=(u[i-1][2][0]+u[i-1][0][-2])%m;
		u[i][1][-2]=u[i-1][2][-1];
		u[i][0][-1]=(u[i-1][0][0]+u[i-1][1][0])%m;
		u[i][0][-2]=(u[i-1][0][-1]+u[i-1][1][-1])%m;
	}
	int mx=0,mn=0;
	long long ans=0;
	for(int i=0;i<n-1;i++){
		if(s[i]=='L'){
			mx+=1;
			mn=min(mn+1,0);
			continue;
		}
		int mx_=mx+1;
		int mn_=min(mn+1,0);
		for(int j=0;j<=2-mx_;j++){
			for(int k=0;k>=-2-mn_;k--){
				ans=(ans+u[n-i-1][j][k])%m;
				//cout << n-i-1 << ' ' << j << ' ' << k << ' ' << u[n-i-1][j][k] << endl;
			}
		}
		mx=max(0,mx-1);
		mn--;
	}
	if(s[n-1]=='P'){
		if(mx!=2) ans++; 
	}
	ans++;
 	ans=ans%m;
	printf("%lld",ans);
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:19:7: warning: unused variable 'o' [-Wunused-variable]
   19 |   int o=0;
      |       ^
linear_garden.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |  scanf("%lld%lld",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
linear_garden.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |   scanf("%c",&s[i]);
      |   ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 4
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5