oj.uz

Submission #95011

# Submission time Handle Problem Language Result Execution time Memory
95011 2019-01-26T17:00:58 Z Retro3014 Linear Garden (IOI08_linear_garden) C++17
100 / 100
 105 ms 52228 KB 
#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])%M;
					}
				}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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #11
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 372 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 424 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1400 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3576 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4140 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16376 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 21104 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 26844 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 32640 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 52228 KB Output is correct
2 Correct 105 ms 52144 KB Output is correct
3 Correct 94 ms 52188 KB Output is correct