Submission #19559825


Source Code Expand

Copy
#include <stdio.h>

const int Mod = 1000000007;

int main()
{
	int N;
	char S[1000001];
	scanf("%d", &N);
	scanf("%s", S);
	if (N == 1) {
		printf("1\n");
		fflush(stdout);
		return 0;
	}
	
	int i, j, cur, prev, flag;
	long long dp[2][4] = {};
	
	for (i = 1; S[i] == S[0]; i++);
	if (i == N) {
		printf("1\n");
		fflush(stdout);
		return 0;
	}
	dp[i%2][0] = i + 1;
	dp[i%2][S[i] - 'A' + 1] = (i + 1) / 2;
	dp[i%2][6 - (S[i] - 'A' + 1) - (S[0] - 'A' + 1)] = i / 2;
	if (i % 2 == 0) flag = S[i] - 'A' + 1;
	else flag = 6 - (S[i] - 'A' + 1) - (S[0] - 'A' + 1);
	
	for (i++, cur = i % 2, prev = 1 - cur; i < N; i++, cur ^= 1, prev ^= 1) {
		for (j = 0; j < 4; j++) dp[cur][j] = 0;
		dp[cur][S[i] - 'A' + 1] = dp[prev][0];
		if (S[i] == 'A') {
			dp[cur][0] = (dp[prev][0] + dp[prev][2] + dp[prev][3] + ((flag != 1)? 1: 0)) % Mod;			
			dp[cur][2] = dp[prev][3];
			dp[cur][3] = dp[prev][2];
			if (flag == 1) flag = 4;
			else if (flag == 2) flag = 3;
			else if (flag == 3) flag = 2;
			else flag = 1;
		} else if (S[i] == 'B') {
			dp[cur][0] = (dp[prev][0] + dp[prev][1] + dp[prev][3] + ((flag != 2)? 1: 0)) % Mod;			
			dp[cur][1] = dp[prev][3];
			dp[cur][3] = dp[prev][1];
			if (flag == 1) flag = 3;
			else if (flag == 2) flag = 4;
			else if (flag == 3) flag = 1;
			else flag = 2;
		} else {
			dp[cur][0] = (dp[prev][0] + dp[prev][1] + dp[prev][2] + ((flag != 3)? 1: 0)) % Mod;			
			dp[cur][1] = dp[prev][2] % Mod;
			dp[cur][2] = dp[prev][1] % Mod;
			if (flag == 1) flag = 2;
			else if (flag == 2) flag = 1;
			else if (flag == 3) flag = 4;
			else flag = 3;
		}
	}
	printf("%lld\n", dp[1-N%2][0]);
	fflush(stdout);
	return 0;
}

Submission Info

Submission Time
Task E - Shorten ABC
User ygussany
Language C (GCC 9.2.1)
Score 800
Code Size 1702 Byte
Status AC
Exec Time 24 ms
Memory 2672 KB

Compile Error

./Main.c: In function ‘main’:
./Main.c:9:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
    9 |  scanf("%d", &N);
      |  ^~~~~~~~~~~~~~~
./Main.c:10:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
   10 |  scanf("%s", S);
      |  ^~~~~~~~~~~~~~

Judge Result

Set Name All Sample
Score / Max Score 800 / 800 0 / 0
Status
AC × 79
AC × 2
Set Name Test Cases
All sample_01.txt, sample_02.txt, testcase_1.txt, testcase_10.txt, testcase_11.txt, testcase_12.txt, testcase_13.txt, testcase_14.txt, testcase_15.txt, testcase_16.txt, testcase_17.txt, testcase_18.txt, testcase_19.txt, testcase_2.txt, testcase_20.txt, testcase_21.txt, testcase_22.txt, testcase_23.txt, testcase_24.txt, testcase_25.txt, testcase_26.txt, testcase_27.txt, testcase_28.txt, testcase_29.txt, testcase_3.txt, testcase_30.txt, testcase_31.txt, testcase_32.txt, testcase_33.txt, testcase_34.txt, testcase_35.txt, testcase_36.txt, testcase_37.txt, testcase_38.txt, testcase_39.txt, testcase_4.txt, testcase_40.txt, testcase_41.txt, testcase_42.txt, testcase_43.txt, testcase_44.txt, testcase_45.txt, testcase_46.txt, testcase_47.txt, testcase_48.txt, testcase_49.txt, testcase_5.txt, testcase_50.txt, testcase_51.txt, testcase_52.txt, testcase_53.txt, testcase_54.txt, testcase_55.txt, testcase_56.txt, testcase_57.txt, testcase_58.txt, testcase_59.txt, testcase_6.txt, testcase_60.txt, testcase_61.txt, testcase_62.txt, testcase_63.txt, testcase_64.txt, testcase_65.txt, testcase_66.txt, testcase_67.txt, testcase_68.txt, testcase_69.txt, testcase_7.txt, testcase_70.txt, testcase_71.txt, testcase_72.txt, testcase_73.txt, testcase_74.txt, testcase_75.txt, testcase_76.txt, testcase_77.txt, testcase_8.txt, testcase_9.txt
Sample sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 1704 KB
sample_02.txt AC 1 ms 1640 KB
testcase_1.txt AC 1 ms 1580 KB
testcase_10.txt AC 1 ms 1600 KB
testcase_11.txt AC 2 ms 1704 KB
testcase_12.txt AC 1 ms 1632 KB
testcase_13.txt AC 1 ms 1632 KB
testcase_14.txt AC 1 ms 1632 KB
testcase_15.txt AC 1 ms 1580 KB
testcase_16.txt AC 2 ms 1580 KB
testcase_17.txt AC 1 ms 1628 KB
testcase_18.txt AC 1 ms 1588 KB
testcase_19.txt AC 1 ms 1584 KB
testcase_2.txt AC 1 ms 1580 KB
testcase_20.txt AC 1 ms 1588 KB
testcase_21.txt AC 1 ms 1632 KB
testcase_22.txt AC 1 ms 1620 KB
testcase_23.txt AC 2 ms 1572 KB
testcase_24.txt AC 1 ms 1584 KB
testcase_25.txt AC 1 ms 1696 KB
testcase_26.txt AC 1 ms 1700 KB
testcase_27.txt AC 1 ms 1584 KB
testcase_28.txt AC 1 ms 1588 KB
testcase_29.txt AC 1 ms 1580 KB
testcase_3.txt AC 1 ms 1584 KB
testcase_30.txt AC 2 ms 1636 KB
testcase_31.txt AC 2 ms 1632 KB
testcase_32.txt AC 1 ms 1580 KB
testcase_33.txt AC 1 ms 1700 KB
testcase_34.txt AC 3 ms 1636 KB
testcase_35.txt AC 2 ms 1644 KB
testcase_36.txt AC 1 ms 1568 KB
testcase_37.txt AC 24 ms 2628 KB
testcase_38.txt AC 19 ms 2668 KB
testcase_39.txt AC 24 ms 2612 KB
testcase_4.txt AC 1 ms 1584 KB
testcase_40.txt AC 20 ms 2612 KB
testcase_41.txt AC 17 ms 2592 KB
testcase_42.txt AC 17 ms 2672 KB
testcase_43.txt AC 18 ms 2672 KB
testcase_44.txt AC 18 ms 2560 KB
testcase_45.txt AC 19 ms 2672 KB
testcase_46.txt AC 17 ms 2608 KB
testcase_47.txt AC 17 ms 2556 KB
testcase_48.txt AC 22 ms 2672 KB
testcase_49.txt AC 16 ms 2612 KB
testcase_5.txt AC 2 ms 1700 KB
testcase_50.txt AC 23 ms 2552 KB
testcase_51.txt AC 17 ms 2668 KB
testcase_52.txt AC 11 ms 2120 KB
testcase_53.txt AC 15 ms 2200 KB
testcase_54.txt AC 11 ms 2172 KB
testcase_55.txt AC 6 ms 1900 KB
testcase_56.txt AC 13 ms 2240 KB
testcase_57.txt AC 11 ms 2488 KB
testcase_58.txt AC 8 ms 2548 KB
testcase_59.txt AC 6 ms 2548 KB
testcase_6.txt AC 1 ms 1640 KB
testcase_60.txt AC 8 ms 2428 KB
testcase_61.txt AC 6 ms 2428 KB
testcase_62.txt AC 6 ms 2532 KB
testcase_63.txt AC 23 ms 2552 KB
testcase_64.txt AC 16 ms 2612 KB
testcase_65.txt AC 14 ms 2612 KB
testcase_66.txt AC 5 ms 2604 KB
testcase_67.txt AC 6 ms 2552 KB
testcase_68.txt AC 10 ms 2672 KB
testcase_69.txt AC 6 ms 2600 KB
testcase_7.txt AC 1 ms 1580 KB
testcase_70.txt AC 6 ms 2612 KB
testcase_71.txt AC 9 ms 2668 KB
testcase_72.txt AC 14 ms 2552 KB
testcase_73.txt AC 19 ms 2668 KB
testcase_74.txt AC 13 ms 2600 KB
testcase_75.txt AC 15 ms 2608 KB
testcase_76.txt AC 19 ms 2628 KB
testcase_77.txt AC 14 ms 2668 KB
testcase_8.txt AC 2 ms 1584 KB
testcase_9.txt AC 2 ms 1584 KB