답안 #920166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
920166	2024-02-02T07:11:07 Z	Ghulam_Junaid	Lottery (CEOI18_lot)	C++17	65 / 100	1080 ms	16216 KB

lot

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int base = 727;

int score[2005][2005];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, l;
    cin >> n >> l;

    int a[n];
    for (int i = 0; i < n; i ++)
        cin >> a[i];

    if (n <= 2000){
        memset(score, 0, sizeof score);
        for (int i = 0; i + l <= n; i ++){
            for (int j = i + 1; j + l <= n; j ++){
                for (int k = 0; k < l; k ++){
                    score[i][j] += (a[i + k] != a[j + k]);
                    score[j][i] += (a[i + k] != a[j + k]);
                }
            }
        }

        for (int i = 0; i + l <= n; i ++)
            sort(score[i], score[i] + n - l + 1);

        int q;
        cin >> q;
        while (q--){
            int k;
            cin >> k;

            for (int i = 0; i + l <= n; i ++){
                int ub = upper_bound(score[i], score[i] + n - l + 1, k) - score[i];
                cout << ub - 1 << " ";
            }
            cout << '\n';
        }

        return 0;
    }

    int Hash[n - l + 1];
    for (int i=0; i+l<=n; i++){
        int hsh = 0;
        for (int j=0; j<l; j++)
            hsh = ((1ll * hsh * base) + a[i + j]) % mod;
        Hash[i] = hsh;
    }

    int q;
    cin >> q;

    while (q--){
        int k;
        cin >> k;

        for (int i = 0; i + l <= n; i ++){
            int ans = -1;
            for (int j = 0; j + l <= n; j ++)
                ans += (Hash[i] == Hash[j]);
            cout << ans << " ";
        }
        cout << endl;
    }
}

Subtask #1

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	15960 KB	Output is correct
2	Correct	4 ms	15960 KB	Output is correct
3	Correct	3 ms	15964 KB	Output is correct
4	Correct	4 ms	15960 KB	Output is correct
5	Correct	3 ms	15960 KB	Output is correct
6	Correct	3 ms	15960 KB	Output is correct
7	Correct	3 ms	15960 KB	Output is correct
8	Correct	6 ms	15960 KB	Output is correct
9	Correct	6 ms	15960 KB	Output is correct
10	Correct	5 ms	16216 KB	Output is correct
11	Correct	5 ms	15960 KB	Output is correct
12	Correct	5 ms	15960 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	15960 KB	Output is correct
2	Correct	4 ms	15960 KB	Output is correct
3	Correct	3 ms	15964 KB	Output is correct
4	Correct	4 ms	15960 KB	Output is correct
5	Correct	3 ms	15960 KB	Output is correct
6	Correct	3 ms	15960 KB	Output is correct
7	Correct	3 ms	15960 KB	Output is correct
8	Correct	6 ms	15960 KB	Output is correct
9	Correct	6 ms	15960 KB	Output is correct
10	Correct	5 ms	16216 KB	Output is correct
11	Correct	5 ms	15960 KB	Output is correct
12	Correct	5 ms	15960 KB	Output is correct
13	Correct	62 ms	15960 KB	Output is correct
14	Correct	880 ms	16168 KB	Output is correct
15	Correct	1080 ms	16208 KB	Output is correct
16	Correct	735 ms	16208 KB	Output is correct
17	Correct	818 ms	16172 KB	Output is correct
18	Correct	779 ms	16172 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	344 KB	Output is correct
2	Correct	63 ms	344 KB	Output is correct
3	Correct	62 ms	524 KB	Output is correct
4	Correct	71 ms	344 KB	Output is correct
5	Correct	139 ms	344 KB	Output is correct
6	Correct	88 ms	596 KB	Output is correct
7	Correct	139 ms	492 KB	Output is correct
8	Correct	134 ms	344 KB	Output is correct
9	Correct	76 ms	344 KB	Output is correct
10	Correct	70 ms	344 KB	Output is correct
11	Correct	13 ms	344 KB	Output is correct
12	Correct	100 ms	344 KB	Output is correct
13	Correct	140 ms	348 KB	Output is correct
14	Correct	141 ms	512 KB	Output is correct

Subtask #4

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	344 KB	Output is correct
2	Correct	63 ms	344 KB	Output is correct
3	Correct	62 ms	524 KB	Output is correct
4	Correct	71 ms	344 KB	Output is correct
5	Correct	139 ms	344 KB	Output is correct
6	Correct	88 ms	596 KB	Output is correct
7	Correct	139 ms	492 KB	Output is correct
8	Correct	134 ms	344 KB	Output is correct
9	Correct	76 ms	344 KB	Output is correct
10	Correct	70 ms	344 KB	Output is correct
11	Correct	13 ms	344 KB	Output is correct
12	Correct	100 ms	344 KB	Output is correct
13	Correct	140 ms	348 KB	Output is correct
14	Correct	141 ms	512 KB	Output is correct
15	Incorrect	74 ms	524 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	15960 KB	Output is correct
2	Correct	4 ms	15960 KB	Output is correct
3	Correct	3 ms	15964 KB	Output is correct
4	Correct	4 ms	15960 KB	Output is correct
5	Correct	3 ms	15960 KB	Output is correct
6	Correct	3 ms	15960 KB	Output is correct
7	Correct	3 ms	15960 KB	Output is correct
8	Correct	6 ms	15960 KB	Output is correct
9	Correct	6 ms	15960 KB	Output is correct
10	Correct	5 ms	16216 KB	Output is correct
11	Correct	5 ms	15960 KB	Output is correct
12	Correct	5 ms	15960 KB	Output is correct
13	Correct	62 ms	15960 KB	Output is correct
14	Correct	880 ms	16168 KB	Output is correct
15	Correct	1080 ms	16208 KB	Output is correct
16	Correct	735 ms	16208 KB	Output is correct
17	Correct	818 ms	16172 KB	Output is correct
18	Correct	779 ms	16172 KB	Output is correct
19	Correct	62 ms	344 KB	Output is correct
20	Correct	63 ms	344 KB	Output is correct
21	Correct	62 ms	524 KB	Output is correct
22	Correct	71 ms	344 KB	Output is correct
23	Correct	139 ms	344 KB	Output is correct
24	Correct	88 ms	596 KB	Output is correct
25	Correct	139 ms	492 KB	Output is correct
26	Correct	134 ms	344 KB	Output is correct
27	Correct	76 ms	344 KB	Output is correct
28	Correct	70 ms	344 KB	Output is correct
29	Correct	13 ms	344 KB	Output is correct
30	Correct	100 ms	344 KB	Output is correct
31	Correct	140 ms	348 KB	Output is correct
32	Correct	141 ms	512 KB	Output is correct
33	Incorrect	74 ms	524 KB	Output isn't correct
34	Halted	0 ms	0 KB	-