# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
500550 | RambaXGorilla | Lottery (CEOI18_lot) | C++17 | 594 ms | 8336 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<cstdio>
#include<algorithm>
using namespace std;
int N, L, Q;
int draws[10010];
int quers[110];
int dists[20010] = {};
int nums[10010] = {};
int sims[110][10010];
int main(){
scanf("%d%d",&N,&L);
for(int i = 0;i < N;i++){
scanf("%d",&draws[i]);
}
scanf("%d",&Q);
for(int i = 0;i < Q;i++){
scanf("%d",&quers[i]);
}
for(int j = 1;j < N - L + 1;j++){
int dist = 0;
for(int i = 0;i < L;i++){
dist += draws[i] != draws[i + j];
}
dists[j + 10000] = dist;
nums[dist]++;
}
for(int i = 1;i < L + 1;i++){
nums[i] += nums[i - 1];
}
for(int j = 0;j < N - L + 1;j++){
for(int i = 0;i < Q;i++){
sims[i][j] = nums[quers[i]];
}
if(j == N - L){
break;
}
fill(nums, nums + 10010, 0);
int dist = 0;
for(int i = 0;i < L;i++){
dist += draws[i] != draws[i + j + 1];
}
dists[-j - 1 + 10000] = dist;
nums[dist]++;
for(int i = -j;i < N - L - j;i++){
if(!i){
continue;
}
dists[i + 10000] -= draws[j] != draws[i + j];
dists[i + 10000] += draws[j + L] != draws[i + j + L];
nums[dists[i + 10000]]++;
}
for(int i = 1;i < L + 1;i++){
nums[i] += nums[i - 1];
}
}
for(int i = 0;i < Q;i++){
for(int j = 0;j < N - L + 1;j++){
printf("%d ",sims[i][j]);
}
printf("\n");
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |