Submission #121450

#	Time	Username	Problem	Language	Result	Execution time	Memory
121450		TadijaSebez	Linear Garden (IOI08_linear_garden)	C++11	100 / 100	26 ms	6248 KiB

linear_garden

#include <stdio.h>
const int N=1000050;
int mod,po[N];
int CountAll(int n){ return (po[n/2+1]+po[(n+1)/2]-2+mod)%mod;}
int CountLo(int n){ return po[n/2];}
int CountHi(int n){ return po[n/2];}
int CountMid(int n){ return po[(n+1)/2];}
char s[N];
int max(int a, int b){ return a>b?a:b;}
int min(int a, int b){ return a>b?b:a;}
int main()
{
	int n,i;
	scanf("%i %i",&n,&mod);
	scanf("%s",s+1);
	int cnt=0,Min=0,Max=0,sol=0;
	po[0]=1;
	for(i=1;i<=n;i++) po[i]=po[i-1]*2%mod;
	for(i=1;i<=n;i++)
	{
		if(s[i]=='L') cnt++,Max=max(Max,cnt),Min=min(Min,cnt);
		else
		{
			if(Max-Min==2)
			{
				if(cnt==Min)
				{
					sol+=CountMid(n-i);
					if(sol>=mod) sol-=mod;
				}
				else if(cnt!=Max)
				{
					sol+=CountHi(n-i);
					if(sol>=mod) sol-=mod;
				}
			}
			else if(Max-Min==1)
			{
				if(cnt==Min)
				{
					sol+=CountMid(n-i)+CountHi(n-i)-1+mod;
					while(sol>=mod) sol-=mod;
				}
				else
				{
					sol+=CountHi(n-i);
					if(sol>=mod) sol-=mod;
				}
			}
			else
			{
				sol+=CountMid(n-i)+CountHi(n-i)-1+mod;
				while(sol>=mod) sol-=mod; 
			}
			cnt--;
			Max=max(Max,cnt);
			Min=min(Min,cnt);
			//printf("%i: %i\n",i,sol);
		}
	}
	sol++;
	if(sol>=mod) sol-=mod;
	printf("%i\n",sol);
	return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&mod);
  ~~~~~^~~~~~~~~~~~~~~~~
linear_garden.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",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