Submission #134170

#	Time	Username	Problem	Language	Result	Execution time	Memory
134170		dragonslayerit	Lottery (CEOI18_lot)	C++14	80 / 100	991 ms	8184 KiB

lot

#include <cstdio>
#include <algorithm>

int as[10001];
std::pair<int,int> ks[101];

int mismatch[10001];

int down[10001];

int ans[100][10001];

int main(){
  int N,L;
  scanf("%d %d",&N,&L);
  for(int i=0;i<N;i++){
    scanf("%d",&as[i]);
  }
  int Q;
  scanf("%d",&Q);
  for(int i=0;i<Q;i++){
    scanf("%d",&ks[i].first);
    ks[i].second=i;
  }
  std::sort(ks,ks+Q);
  ks[Q].first=10001;
  for(int x=0;x<=10000;x++){
    for(int q=0;q<=Q;q++){
      if(x<=ks[q].first){
	down[x]=q;
	break;
      }
    }
  }
  for(int shift=1;shift+L<=N;shift++){
    std::fill(mismatch,mismatch+N-L-shift+1,0);
    for(int i=0;i+shift<N;i++){
      if(as[i]!=as[i+shift]){
	mismatch[std::max(0,i-L+1)]++;
	mismatch[std::min(i,N-L-shift)+1]--;
      }
    }
    for(int i=1;i<=N-L-shift;i++){
      mismatch[i]+=mismatch[i-1];
    }
    /*
    for(int q=0;q<Q;q++){
      for(int i=0;i<=N-L-shift;i++){
	//printf("[%d,%d] and [%d,%d]: %d\n",i,i+L-1,i+shift,i+shift+L-1,mismatch[i]);
	if(mismatch[i]<=ks[q].first){
	  ans[q][i]++;
	  ans[q][i+shift]++;
	}
      }
    }
    */
    for(int i=0;i<=N-L-shift;i++){
      ans[down[mismatch[i]]][i]++;
      ans[down[mismatch[i]]][i+shift]++;
    }
  }
  for(int q=1;q<Q;q++){
    for(int i=0;i<=N-L;i++){
      ans[q][i]+=ans[q-1][i];
    }
  }
  for(int q=0;q<Q;q++){
    for(int k=0;k<Q;k++){
      if(ks[k].second==q){
	for(int i=0;i<=N-L;i++){
	  if(i) printf(" ");
	  printf("%d",ans[k][i]);
	}
	printf("\n");
	break;
      }
    }
  }
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&N,&L);
   ~~~~~^~~~~~~~~~~~~~~
lot.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&as[i]);
     ~~~~~^~~~~~~~~~~~~
lot.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&Q);
   ~~~~~^~~~~~~~~
lot.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&ks[i].first);
     ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20