Submission #428419

#	Time	Username	Problem	Language	Result	Execution time	Memory
428419		jamielim	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	26 ms	10040 KiB

linear_garden

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

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n,m;
char str[1000005];
ll two[1000005];

ll dp(int x,int l,int h,int c){
	//printf("%d %d %d %d\n",x,l,h,c);
	if(h-l>2||c>=5||c<0)return 0;
	ll ans=0;
	if(h-l==2){
		if(c==(l+h)/2)ans=two[(x+1)/2];
		else ans=two[x/2];
	}else{ // 1
		ans=two[x/2]+two[(x+1)/2]-1;
	}
	return ans%m;
}

int main(){
	scanf("%d%d %s",&n,&m,str);
	two[0]=1;for(int i=1;i<1000005;i++)two[i]=(two[i-1]*2LL)%m;
	ll ans=0;
	int lo=2,hi=2,cur=2;
	for(int i=0;i<n;i++){
		if(str[i]=='L')cur++;
		else{
			ans+=dp(n-i-1,lo,max(cur+1,hi),cur+1);
			//printf("%lld\n",dp(n-i-1,lo,max(cur+1,hi),cur+1));
			cur--;
		}
		lo=min(cur,lo);hi=max(cur,hi);
		ans%=m;
	}
	printf("%lld",(ans+m+1)%m);
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d%d %s",&n,&m,str);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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