Submission #134156

#	Time	Username	Problem	Language	Result	Execution time	Memory
134156		dragonslayerit	Lottery (CEOI18_lot)	C++14	80 / 100	3029 ms	3376 KiB

lot

#include <cstdio>
#include <algorithm>

int as[10001];
int ks[101];

int mismatch[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]);
  }
  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]){
	  ans[q][i]++;
	  ans[q][i+shift]++;
	}
      }
    }
  }
  for(int q=0;q<Q;q++){
    for(int i=0;i<=N-L;i++){
      if(i) printf(" ");
      printf("%d",ans[q][i]);
    }
    printf("\n");
  }
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:13: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:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&as[i]);
     ~~~~~^~~~~~~~~~~~~
lot.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&Q);
   ~~~~~^~~~~~~~~
lot.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&ks[i]);
     ~~~~~^~~~~~~~~~~~~

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