oj.uz

Submission #161372

# Submission time Handle Problem Language Result Execution time Memory
161372 2019-11-02T05:35:33 Z rama_pang Lottery (CEOI18_lot) C++14
35 / 100
 937 ms 632 KB 
#include <bits/stdc++.h>
using namespace std;

int N, L, q, A[10005];
int ans[100][10005];
pair<int, int> Q[100];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> L; for (int i = 0; i < N; i++) cin >> A[i];
    cin >> q; for (int i = 0; i < q; i++) cin >> Q[i].first;
    for (int i = 0; i < q; i++) Q[i].second = i;
    sort(Q, Q + q);

    /* The segment compared is segment i...(i + L - 1) and (i + shift)...(i + L + shift - 1) */
    for (int shift = 1, similiar = 0; shift + L - 1 < N; shift++, similiar = 0) {
        for (int i = 0; i < L; i++) 
            if (A[i] == A[i + shift]) similiar++;
        
        for (int i = 0; i + shift + L - 1 < N; i++) { // then sliding window can be used
            int j = lower_bound(Q, Q + q, make_pair(L - similiar, -1)) - Q;
            ans[j][i]++, ans[j][i + shift]++; // Add 1 to the answer for the lowest Q possible

            if (A[i] == A[i + shift]) similiar--;
            if (A[i + L] == A[i + shift + L]) similiar++;
        }
    }
    /* If Q[i] <= Q[j], then all answers from Q[i] can be used in Q[j] */
    for (int i = 0; i < N; i++) 
        for (int j = 1; j < q; j++) 
            ans[j][i] += ans[j - 1][i];

    for (int i = 0; i < q; i++) {
        for (int j = 0; j < N - L + 1; j++) 
            cout << ans[i][j] << " ";

        cout << "\n";
    }
}

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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 504 KB Output is correct
2 Correct 937 ms 520 KB Output is correct
3 Correct 492 ms 504 KB Output is correct
4 Correct 415 ms 632 KB Output is correct
5 Correct 129 ms 504 KB Output is correct
6 Correct 391 ms 504 KB Output is correct
7 Correct 86 ms 504 KB Output is correct
8 Correct 148 ms 476 KB Output is correct
9 Correct 397 ms 632 KB Output is correct
10 Correct 415 ms 504 KB Output is correct
11 Correct 52 ms 380 KB Output is correct
12 Correct 235 ms 580 KB Output is correct
13 Correct 321 ms 504 KB Output is correct
14 Correct 185 ms 504 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 504 KB Output is correct
2 Correct 937 ms 520 KB Output is correct
3 Correct 492 ms 504 KB Output is correct
4 Correct 415 ms 632 KB Output is correct
5 Correct 129 ms 504 KB Output is correct
6 Correct 391 ms 504 KB Output is correct
7 Correct 86 ms 504 KB Output is correct
8 Correct 148 ms 476 KB Output is correct
9 Correct 397 ms 632 KB Output is correct
10 Correct 415 ms 504 KB Output is correct
11 Correct 52 ms 380 KB Output is correct
12 Correct 235 ms 580 KB Output is correct
13 Correct 321 ms 504 KB Output is correct
14 Correct 185 ms 504 KB Output is correct
15 Correct 457 ms 504 KB Output is correct
16 Correct 362 ms 612 KB Output is correct
17 Correct 452 ms 632 KB Output is correct
18 Correct 430 ms 632 KB Output is correct
19 Correct 424 ms 376 KB Output is correct
20 Correct 426 ms 632 KB Output is correct
21 Correct 418 ms 536 KB Output is correct

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 -