oj.uz

답안 #121450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
121450 2019-06-26T14:17:37 Z TadijaSebez Linear Garden (IOI08_linear_garden) C++11
100 / 100
 26 ms 6248 KB 
#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

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.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #7
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #8
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #9
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #10
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #11
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 352 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 700 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 768 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 2176 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2748 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 3368 KB Output is correct

Subtask #22
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 3960 KB Output is correct

Subtask #23
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 6248 KB Output is correct
2 Correct 22 ms 6120 KB Output is correct
3 Correct 26 ms 6124 KB Output is correct