POJ 3370 Halloween treats

問題

n個の整数が与えられる。
この中から適当な(空でない)部分集合を選び、その要素の和がcの倍数にすることはできるか。

できるならそのような集合(どれでもよい)の要素を全て出力し、
不可能なら"no sweets"と出力せよ。

制約条件

1≦c≦n≦100000

方針

愚直にDPすると、O(cn)かかって明らかにTLE.


c≦nという制約に注目する。
sum[i]=(Σ[k≦i]a[k]) mod cとする。
すると、sumは0〜c-1までのc通りの値しか取らないから、必ず
i≠jでsum[i]=sum[j]となるi,jが存在する。


そのようなi,jを見つけたら、
a[i+1], a[i+2], ..., a[j]が答えである。


これでO(n)で出来る。
のだがやたら制限時間が厳しく、O(n)なのに制限時間ギリギリになる。

ソースコード

int c,n,a[100001];
int index[100001];

int main()
{
	while(scanf("%d%d",&c,&n),c){
		rep(i,n)scanf("%d",a+i), index[i]=-1;
		int sum=0;
		rep(i,n){
			(sum+=a[i])%=c;
			if(sum==0){
				rep(j,i+1)
					printf("%d%c",j+1,j==i?'\n':' ');
				break;
			}
			if(index[sum]>=0){
				for(int j=index[sum]+1;j<=i;j++)
					printf("%d%c",j+1,j==i?'\n':' ');
				break;
			}
			index[sum]=i;
		}
	}
	return 0;
}