poj 2356 Find a multiple(ハトの巣の原理+マーク)

タイトル:http://poj.org/problem?id=2356
n個の数字を与えて、その中で連続する数字を探し出してそれとnの倍数であるようにして、出力0を探し当てることができません.
sum[i]=a 1+a 2+......+ai,n個のsum[i]モードnの結果範囲を[0,n−1]とする.ハトの巣の原理から,必ず1つのsum[i]のモジュール結果が0(均一分布)であるか,または2つのsum[i]のモジュール結果が等しい(非均一分布)(すなわちsum[j]−sum[i]=0)ことが分かった.このような連続数字の和がnの倍数であることは間違いない.N<=1 e 4では,純暴力でタイムアウトのリスクがある場合,空間的に時間を変える場合には,「必ず1つのsum[i]のモジュール結果が0または2つのsum[i]のモジュール結果が等しい」としてマーキング法を用いる.

#include <iostream>
#include <cstdio>
#include<cstring>
using namespace std;
const int maxn=1e4+5;
int sum[maxn],tag[maxn],a[maxn],l,r,N;
int main()
{
    //freopen("cin.txt","r",stdin);
    while(cin>>N){
        memset(sum,0,sizeof(sum));
        memset(tag,-1,sizeof(tag));
        tag[0]=0;
        for(int i=1;i<=N;i++){
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
            int m=sum[i]%N;
            if(tag[m]==-1) tag[m]=i;
            else {
                l=tag[m];
                r=i;
            }
        }
        printf("%d
",r-l);
        for(int i=l+1;i<=r;i++){
            printf("%d
",a[i]);
        }
    }
    return 0;
}