Submission #500550

#	Time	Username	Problem	Language	Result	Execution time	Memory
500550		RambaXGorilla	Lottery (CEOI18_lot)	C++17	100 / 100	594 ms	8336 KiB

lot

#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)

lot.cpp: In function 'int main()':
lot.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d%d",&N,&L);
      |     ~~~~~^~~~~~~~~~~~~~
lot.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%d",&draws[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
lot.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
lot.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d",&quers[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

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