Submission #198899

#	Time	Username	Problem	Language	Result	Execution time	Memory
198899		arnold518	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	24 ms	10104 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

int N, M, dp[MAXN+10][2], ans=1;
char S[MAXN+10];

int main()
{
	int i, j;

	scanf("%d%d%s", &N, &M, S+1);

	dp[0][0]=dp[0][1]=1;
	for(i=1; i<=N; i++)
	{
		dp[i][0]=dp[i-1][1];
		dp[i][1]=(dp[i-1][0]*2)%M;
	}

	int a=0, b=0, c=0;
	for(i=1; i<=N; i++)
	{
		if(S[i]=='P')
		{
			int cc=c+1;
			int aa=min(a, cc), bb=max(b, cc);
			if(bb-aa<=2)
			{
				int d=0;
				if(cc-1<=aa && bb<=cc+1) d++, ans+=dp[N-i][1];
				if(cc-2<=aa && bb<=cc) d++, ans+=dp[N-i][0];
				ans%=M;
				if(d==2) ans--, ans=(ans+M)%M;
			}
		}

		if(S[i]=='L') c++;
		else c--;
		a=min(a, c); b=max(b, c);
	}

	printf("%d", ans);
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:15:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
linear_garden.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%s", &N, &M, S+1);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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