提出 #20050076

ソースコード 拡げる

/*
after dusk passed,
there is a starry sky.
*/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define m_k make_pair
#define mod 1000000007
using namespace std;
const int N=1e6+100;
int n,sum[N],a[N],dp[N],r[N];
char s[N];
vector <int> mp[4];
inline void add(int &a,int b){a=((a+b>=mod)?a+b-mod:a+b);}
inline void del(int &a,int b){a=((a-b<0)?a-b+mod:a-b);}
inline void mul(int &a,int b){a=1ll*a*b%mod;}
inline int m_pow(int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1) mul(ans,a);
		b>>=1;
		mul(a,a);
	}
	return ans;
}
inline int read()
{
	int f=1,x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}
signed main()
{
	n=read();
	scanf("%s",s+1);
	for (int i=1;i<=n;i++) a[i]=(s[i]=='A'?1:(s[i]=='B'?2:3));
	for (int i=1;i<=n;i++) sum[i]=sum[i-1]^a[i];
	bool bl=1;
	for (int i=2;i<=n;i++) if (s[i]!=s[1]) bl=0;
	if (bl)
	{
		printf("1\n");
		return 0;
	}
	for (int i=n;i>=1;i--) mp[sum[i]].push_back(i);
	dp[0]=1;
	for (int i=0;i<n;i++)
	{
		for (int j=1;j<=3;j++)
		{
			int x=sum[i]^j;
			while (!mp[x].empty()&&mp[x].back()<=i) mp[x].pop_back();
			if (mp[x].empty()) continue;
			x=mp[x].back();
			add(dp[x],dp[i]);
		}
	}
	int ans=0;
	for (int i=1;i<=n;i++) if (!(sum[n]^sum[i])) add(ans,dp[i]);
	printf("%d\n",ans);
}

提出情報

提出日時
問題 E - Shorten ABC
ユーザ SevenDawns
言語 C++ (GCC 9.2.1)
得点 800
コード長 1376 Byte
結果 AC
実行時間 52 ms
メモリ 21412 KiB

コンパイルエラー

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

ジャッジ結果

セット名 All Sample
得点 / 配点 800 / 800 0 / 0
結果
AC × 79
AC × 2
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
sample_01.txt AC 6 ms 3752 KiB
sample_02.txt AC 2 ms 3704 KiB
testcase_1.txt AC 2 ms 3448 KiB
testcase_10.txt AC 2 ms 3748 KiB
testcase_11.txt AC 2 ms 3704 KiB
testcase_12.txt AC 2 ms 3740 KiB
testcase_13.txt AC 3 ms 3756 KiB
testcase_14.txt AC 2 ms 3700 KiB
testcase_15.txt AC 2 ms 3708 KiB
testcase_16.txt AC 2 ms 3636 KiB
testcase_17.txt AC 2 ms 3720 KiB
testcase_18.txt AC 2 ms 3740 KiB
testcase_19.txt AC 2 ms 3808 KiB
testcase_2.txt AC 2 ms 3508 KiB
testcase_20.txt AC 2 ms 3596 KiB
testcase_21.txt AC 2 ms 3708 KiB
testcase_22.txt AC 2 ms 3708 KiB
testcase_23.txt AC 2 ms 3496 KiB
testcase_24.txt AC 3 ms 3720 KiB
testcase_25.txt AC 2 ms 3700 KiB
testcase_26.txt AC 2 ms 3708 KiB
testcase_27.txt AC 2 ms 3736 KiB
testcase_28.txt AC 2 ms 3620 KiB
testcase_29.txt AC 2 ms 3704 KiB
testcase_3.txt AC 3 ms 3640 KiB
testcase_30.txt AC 2 ms 3624 KiB
testcase_31.txt AC 2 ms 3568 KiB
testcase_32.txt AC 4 ms 3720 KiB
testcase_33.txt AC 2 ms 3720 KiB
testcase_34.txt AC 2 ms 3640 KiB
testcase_35.txt AC 2 ms 3712 KiB
testcase_36.txt AC 2 ms 3748 KiB
testcase_37.txt AC 51 ms 19928 KiB
testcase_38.txt AC 49 ms 19952 KiB
testcase_39.txt AC 50 ms 20000 KiB
testcase_4.txt AC 2 ms 3812 KiB
testcase_40.txt AC 48 ms 19980 KiB
testcase_41.txt AC 52 ms 19892 KiB
testcase_42.txt AC 51 ms 19896 KiB
testcase_43.txt AC 51 ms 19844 KiB
testcase_44.txt AC 48 ms 19956 KiB
testcase_45.txt AC 52 ms 19968 KiB
testcase_46.txt AC 47 ms 20120 KiB
testcase_47.txt AC 51 ms 20092 KiB
testcase_48.txt AC 49 ms 20080 KiB
testcase_49.txt AC 52 ms 19972 KiB
testcase_5.txt AC 2 ms 3596 KiB
testcase_50.txt AC 48 ms 19976 KiB
testcase_51.txt AC 50 ms 19956 KiB
testcase_52.txt AC 28 ms 11400 KiB
testcase_53.txt AC 39 ms 13900 KiB
testcase_54.txt AC 34 ms 12480 KiB
testcase_55.txt AC 15 ms 7352 KiB
testcase_56.txt AC 41 ms 14560 KiB
testcase_57.txt AC 23 ms 12460 KiB
testcase_58.txt AC 15 ms 12428 KiB
testcase_59.txt AC 18 ms 12392 KiB
testcase_6.txt AC 2 ms 3808 KiB
testcase_60.txt AC 27 ms 12384 KiB
testcase_61.txt AC 19 ms 12388 KiB
testcase_62.txt AC 16 ms 12424 KiB
testcase_63.txt AC 40 ms 21176 KiB
testcase_64.txt AC 37 ms 21412 KiB
testcase_65.txt AC 38 ms 21096 KiB
testcase_66.txt AC 38 ms 20052 KiB
testcase_67.txt AC 40 ms 19976 KiB
testcase_68.txt AC 37 ms 20056 KiB
testcase_69.txt AC 39 ms 20036 KiB
testcase_7.txt AC 4 ms 3636 KiB
testcase_70.txt AC 34 ms 20036 KiB
testcase_71.txt AC 37 ms 20004 KiB
testcase_72.txt AC 37 ms 20004 KiB
testcase_73.txt AC 37 ms 20036 KiB
testcase_74.txt AC 41 ms 20008 KiB
testcase_75.txt AC 39 ms 20036 KiB
testcase_76.txt AC 38 ms 19976 KiB
testcase_77.txt AC 40 ms 20052 KiB
testcase_8.txt AC 5 ms 3636 KiB
testcase_9.txt AC 2 ms 3704 KiB