oj.uz

Submission #134162

# Submission time Handle Problem Language Result Execution time Memory
134162 2019-07-22T07:37:43 Z dragonslayerit Lottery (CEOI18_lot) C++14
0 / 100
 871 ms 540 KB 
#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);
  for(int i=0;i<Q;i++){
    for(int x=ks[i].first;x<=10000;x++){
      down[x]=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].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

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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 871 ms 540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 871 ms 540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -