Submission #95010

#	Time	Username	Problem	Language	Result	Execution time	Memory
95010		Retro3014	Linear Garden (IOI08_linear_garden)	C++17	90 / 100	108 ms	53228 KiB

linear_garden

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <string>

using namespace std;
#define MAX_N 1000001


int DP[MAX_N+1][13];
int N, M;
char str[MAX_N+1];
int ans = 0;

void f1(int x, int y, int z){
	DP[x][y] = DP[x+1][z];
}

void f2(int x, int y, int z, int w){
	DP[x][y] = (DP[x+1][z]+DP[x+1][w])%M;
}

int main(){
	scanf("%d%d", &N, &M);
	getchar();
	for(int i=0; i<N; i++){
		scanf("%c", &str[i]);
	}
	for(int i=0; i<N; i++){
		if(str[i]=='L')		str[i] = 1;
		else	str[i] = 0;
	}
	for(int i=0; i<13; i++)	DP[N][i] = 1;
	for(int i=N-1; i>=0; i--){
		f2(i, 0, 2, 1);f2(i, 1, 12, 0);f1(i, 2, 3);f2(i, 3, 2, 4);f1(i, 4, 3);f2(i, 5, 10, 6);f2(i, 6, 9, 5);f1(i, 7, 8);f2(i, 8, 7, 9);f1(i, 9, 8);f1(i, 10, 11);f2(i, 11, 10, 12);f1(i, 12, 11);
	}
	/*for(int i=0; i<=N; i++){
		for(int j=0; j<13; j++){
			printf("%d %d %d\n", i, j, DP[i][j]);
		}
	}*/
	int st = 2, u = 2, d = 2;
	for(int i=0; i<N; i++){
		if(str[i]==1){
			st++;
			u = max(st, u);
			d = min(st, d);
		}else{
			st++;
			int uu=max(st, u), dd = min(st, d);
			//cout<<st<<" "<<uu<<" "<<dd<<endl;
			int pans = ans;
			if(st<=4){
				if(st==4){
					if(uu==4 && dd==2)	ans=(ans+DP[i+1][2])%M;
				}else if(st==3){
					if(uu==4){
						if(dd==2)	ans = (ans+DP[i+1][3])%M;
					}else if(uu==3){
						if(dd==2)	ans = (ans+DP[i+1][0])%M;
						else if(dd==1)	ans = (ans+DP[i+1][10]);
					}
				}else if(st==2){
					if(uu==4){
						if(dd==2)	ans = (ans+DP[i+1][4])%M;
					}else if(uu==3){
						if(dd==2)	ans = (ans+DP[i+1][1])%M;
						else if(dd==1)	ans = (ans+DP[i+1][11])%M;
					}else if(uu==2){
						if(dd==1)	ans = (ans+DP[i+1][5])%M;
						else if(dd==0)	ans = (ans+DP[i+1][7])%M;
					}
				}else if(st==1){
					if(uu==2 && dd==0)	ans = (ans+DP[i+1][8])%M;
				}
			}
			//printf("%d\n", (ans-pans+M)%M);
			st-=2;
			u = max(st, u); d = min(st, d);
		}
	}
	printf("%d", (ans+1)%M);
	return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:53:8: warning: unused variable 'pans' [-Wunused-variable]
    int pans = ans;
        ^~~~
linear_garden.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
linear_garden.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &str[i]);
   ~~~~~^~~~~~~~~~~~~~~

• 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: 0 / 5
• Subtask 19: 5 / 5
• Subtask 20: 0 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5