Submission #119036

#	Time	Username	Problem	Language	Result	Execution time	Memory
119036		baluteshih	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	50 ms	25940 KiB

linear_garden

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int MOD;
int PP[3][1000005],PL[3][1000005]; 
string s;

void calPL(int n)
{
	for(int i=2;i<=n;++i)
	{
		PL[0][i]=PL[2][i]=PL[1][i]=0;
		if(i&1) PL[0][i]=1;
		PL[0][i]=(PL[0][i]+PL[1][i-1])%MOD;
		PL[1][i]=(PL[0][i-1]+PL[2][i-1])%MOD;
		PL[2][i]=(PL[2][i]+PL[1][i-1])%MOD;
	}
}

void calPP(int n)
{
	for(int i=2;i<=n;++i)
	{
		PP[0][i]=PP[2][i]=PP[1][i]=0;
		if(i&1^1) PP[2][i]=1;
		PP[0][i]=(PP[0][i]+PP[1][i-1])%MOD;
		PP[1][i]=(PP[0][i-1]+PP[2][i-1])%MOD;
		PP[2][i]=(PP[2][i]+PP[1][i-1])%MOD;
	}
}

int range(int x,int n)
{
	if(x==2)
		return (PP[0][n]+PP[1][n]+PP[2][n])%MOD;
	else
		return (PL[0][n]+PL[1][n]+PL[2][n])%MOD;
}

int main()
{jizz
	int n,ans=0,rv=0,flag=0,all,nw;
	cin >> n >> MOD >> s;
	if(n==1)
		if(s=="L") cout << "1\n";
		else cout << "2\n";
	else if(n==2)
		if(s=="LL") cout << "1\n";
		else if(s=="LP") cout << "2\n";
		else if(s=="PL") cout << "3\n";
		else cout << "4\n";
	else
	{
		if(s[0]=='L') 
		{
			rv=1;
			for(auto &c:s)
				if(c=='L') c='P';
				else c='L';
		}
		calPP(n),calPL(n);
		ans=(range(1,n)+range(2,n)+1)%MOD;
		all=ans*2%MOD;
		nw=1;
		for(int i=1;i<n;++i)
		{
			if(!flag)
				if(i&1)
					if(s[i]=='L');
					else
						flag=1,ans=(ans+range(1,n-i)+range(2,n-i)+1)%MOD;
				else
					if(s[i]=='L') flag=-1;
					else
						ans=(ans+range(1,n-i)+1)%MOD;
			else if(s[i]=='P')
				if(nw==1)
					if(flag==1)
						ans=(ans+range(1,n-i)+1)%MOD;
					else
						ans=(ans+range(2,n-i)+1)%MOD;
				else if(nw==0)
					if(flag==-1)
						ans=(ans+range(1,n-i)+1)%MOD;
			if(s[i]=='P') ++nw;
			else --nw;
		}
		if(rv) cout << (all-ans+MOD)%MOD << "\n";
		else cout << (ans+1)%MOD << "\n";
	}
}

Compilation message (stderr)

linear_garden.cpp: In function 'void calPP(int)':
linear_garden.cpp:37:7: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   if(i&1^1) PP[2][i]=1;
      ~^~
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:88:11: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
    else if(s[i]=='P')
           ^

• 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