Submission #36748892

Source Code Expand

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
void Inc(int &a, const int &b)
{
	((a += b) >= MOD) && (a -= MOD);
}
const int N = 2e6 + 5;
int n, a[N], xors[N];
char ch[N];
int len[N][4];
int f[N], ans;
int main()
{
	scanf("%d", &n);
	scanf("%s", ch + 1);
	bool same = 1;
	for(int i = 1; i <= n; ++i)
	{
		a[i] = ch[i] - 'A' + 1;
		xors[i] = xors[i - 1] ^ a[i];
		if(i > 1 && a[i] != a[i - 1] && same)
			same = 0; 
	}
	if(same)
	{
		puts("1");
		return 0;
	}
	for(int i = 1; i <= 3; ++i)
		len[n + 1][i] = n + 1;
	for(int i = n; i >= 0; --i)
		for(int j = 1; j <= 3; ++j)
		{
			if(a[i] == j) len[i][j] = 1;
			else len[i][j] = len[i + 1][j ^ a[i]] + 1;
		}
	f[0] = 1;
	for(int i = 0; i <= n; ++i)
		for(int j = 1; j <= 3; ++j)
			Inc(f[i + len[i + 1][j]], f[i]);
	for(int i = 1; i <= n; ++i)
		if(!(xors[i] ^ xors[n]))
			Inc(ans, f[i]);
	printf("%d\n", ans);
	return 0;
}

Submission Info

Submission Time
Task E - Shorten ABC
User Schucking_Sattin
Language C++ (GCC 9.2.1)
Score 800
Code Size 963 Byte
Status AC
Exec Time 49 ms
Memory 32156 KiB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:16:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   16 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
./Main.cpp:17:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf("%s", ch + 1);
      |  ~~~~~^~~~~~~~~~~~~~

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 10 ms 3732 KiB
sample_02.txt AC 2 ms 3600 KiB
testcase_1.txt AC 2 ms 3696 KiB
testcase_10.txt AC 1 ms 3652 KiB
testcase_11.txt AC 2 ms 3720 KiB
testcase_12.txt AC 2 ms 3776 KiB
testcase_13.txt AC 2 ms 3812 KiB
testcase_14.txt AC 1 ms 3720 KiB
testcase_15.txt AC 2 ms 3772 KiB
testcase_16.txt AC 2 ms 3728 KiB
testcase_17.txt AC 2 ms 3664 KiB
testcase_18.txt AC 2 ms 3716 KiB
testcase_19.txt AC 2 ms 3836 KiB
testcase_2.txt AC 2 ms 3700 KiB
testcase_20.txt AC 2 ms 3836 KiB
testcase_21.txt AC 2 ms 3828 KiB
testcase_22.txt AC 2 ms 3732 KiB
testcase_23.txt AC 2 ms 3696 KiB
testcase_24.txt AC 2 ms 3836 KiB
testcase_25.txt AC 2 ms 3780 KiB
testcase_26.txt AC 2 ms 3772 KiB
testcase_27.txt AC 2 ms 3648 KiB
testcase_28.txt AC 2 ms 3740 KiB
testcase_29.txt AC 2 ms 3676 KiB
testcase_3.txt AC 2 ms 3516 KiB
testcase_30.txt AC 2 ms 3596 KiB
testcase_31.txt AC 3 ms 3732 KiB
testcase_32.txt AC 2 ms 3724 KiB
testcase_33.txt AC 2 ms 3600 KiB
testcase_34.txt AC 2 ms 3656 KiB
testcase_35.txt AC 2 ms 3736 KiB
testcase_36.txt AC 2 ms 3536 KiB
testcase_37.txt AC 43 ms 32148 KiB
testcase_38.txt AC 49 ms 31924 KiB
testcase_39.txt AC 43 ms 32048 KiB
testcase_4.txt AC 2 ms 3728 KiB
testcase_40.txt AC 42 ms 32156 KiB
testcase_41.txt AC 44 ms 31912 KiB
testcase_42.txt AC 42 ms 32044 KiB
testcase_43.txt AC 42 ms 32148 KiB
testcase_44.txt AC 42 ms 31992 KiB
testcase_45.txt AC 42 ms 31916 KiB
testcase_46.txt AC 41 ms 31956 KiB
testcase_47.txt AC 42 ms 31916 KiB
testcase_48.txt AC 44 ms 31960 KiB
testcase_49.txt AC 43 ms 32056 KiB
testcase_5.txt AC 2 ms 3720 KiB
testcase_50.txt AC 46 ms 31912 KiB
testcase_51.txt AC 42 ms 31912 KiB
testcase_52.txt AC 25 ms 17508 KiB
testcase_53.txt AC 28 ms 21580 KiB
testcase_54.txt AC 24 ms 19160 KiB
testcase_55.txt AC 14 ms 10952 KiB
testcase_56.txt AC 35 ms 22684 KiB
testcase_57.txt AC 14 ms 12316 KiB
testcase_58.txt AC 18 ms 12304 KiB
testcase_59.txt AC 13 ms 12448 KiB
testcase_6.txt AC 3 ms 3720 KiB
testcase_60.txt AC 12 ms 12308 KiB
testcase_61.txt AC 15 ms 12448 KiB
testcase_62.txt AC 13 ms 12448 KiB
testcase_63.txt AC 36 ms 32036 KiB
testcase_64.txt AC 31 ms 31916 KiB
testcase_65.txt AC 40 ms 31916 KiB
testcase_66.txt AC 37 ms 32040 KiB
testcase_67.txt AC 36 ms 31992 KiB
testcase_68.txt AC 35 ms 32040 KiB
testcase_69.txt AC 37 ms 32124 KiB
testcase_7.txt AC 2 ms 3776 KiB
testcase_70.txt AC 36 ms 32092 KiB
testcase_71.txt AC 37 ms 32092 KiB
testcase_72.txt AC 33 ms 32056 KiB
testcase_73.txt AC 37 ms 31916 KiB
testcase_74.txt AC 39 ms 31912 KiB
testcase_75.txt AC 36 ms 31912 KiB
testcase_76.txt AC 36 ms 31916 KiB
testcase_77.txt AC 37 ms 31956 KiB
testcase_8.txt AC 2 ms 3780 KiB
testcase_9.txt AC 2 ms 3596 KiB