oj.uz

Submission #77956

# Submission time Handle Problem Language Result Execution time Memory
77956 2018-10-01T12:08:51 Z Saboon Lottery (CEOI18_lot) C++14
100 / 100
 680 ms 15952 KB 
#include <iostream>
#include <queue>
#include <stack>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <cmath>
#include <cassert>
#include <unordered_set>
#include <map>
#include <deque>
#include <unordered_map>
#include <fstream>
#include <set>
#include <algorithm>
#include <iomanip>
#define fin cin
#define fout cout
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int maxn = 10000 + 10;

int a[maxn], nex[maxn], dp[maxn][110];
pii q[maxn];
vector <int> v[maxn];

int n, l;

int similar (int fi, int se) {
    int ret = 0;
    for (int x = 0; x < l; x++)
        ret += (a[fi + x] != a[se + x]);
    return ret;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin >> n >> l;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        cin >> q[i].F;
        q[i].S = i;
    }
    sort (q, q + Q);
    for (int i = l; i >= 0; i--) {
        nex[i] = lower_bound (q, q + Q, MP (i, 0)) - q;
    }
    for (int dis = 1; dis < n - l + 1; dis++) {
        int cnt = similar (0, dis);
        dp[0][nex[cnt]] ++;
        dp[dis][nex[cnt]] ++;
        for (int i = 0; i < n - l - dis; i++) {
            cnt -= (a[i] != a[(i + dis) % n]);
            cnt += (a[i + l] != a[i + dis + l]);
            dp[i + 1][nex[cnt]] ++;
            dp[i + dis + 1][nex[cnt]] ++;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < Q - 1; j++) {
            dp[i][j + 1] += dp[i][j];
        }
    }
    for (int i = 0; i < Q; i++) {
        for (int j = 0; j < n - l + 1; j++) {
            v[q[i].S].PB (dp[j][i]);
        }
    }
    for (int j = 0; j < Q; j++) {
        for (auto w : v[j])
            cout << w << " ";
        cout << endl;
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 2 ms 756 KB Output is correct
3 Correct 3 ms 816 KB Output is correct
4 Correct 2 ms 816 KB Output is correct
5 Correct 2 ms 836 KB Output is correct
6 Correct 2 ms 836 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 3 ms 956 KB Output is correct
9 Correct 3 ms 1008 KB Output is correct
10 Correct 3 ms 1128 KB Output is correct
11 Correct 3 ms 1128 KB Output is correct
12 Correct 4 ms 1128 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 2 ms 756 KB Output is correct
3 Correct 3 ms 816 KB Output is correct
4 Correct 2 ms 816 KB Output is correct
5 Correct 2 ms 836 KB Output is correct
6 Correct 2 ms 836 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 3 ms 956 KB Output is correct
9 Correct 3 ms 1008 KB Output is correct
10 Correct 3 ms 1128 KB Output is correct
11 Correct 3 ms 1128 KB Output is correct
12 Correct 4 ms 1128 KB Output is correct
13 Correct 21 ms 1868 KB Output is correct
14 Correct 16 ms 2004 KB Output is correct
15 Correct 13 ms 2004 KB Output is correct
16 Correct 21 ms 2080 KB Output is correct
17 Correct 29 ms 2080 KB Output is correct
18 Correct 18 ms 2084 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 5564 KB Output is correct
2 Correct 561 ms 5700 KB Output is correct
3 Correct 623 ms 5716 KB Output is correct
4 Correct 578 ms 5732 KB Output is correct
5 Correct 225 ms 5732 KB Output is correct
6 Correct 497 ms 5732 KB Output is correct
7 Correct 165 ms 5732 KB Output is correct
8 Correct 298 ms 5732 KB Output is correct
9 Correct 517 ms 6108 KB Output is correct
10 Correct 537 ms 6308 KB Output is correct
11 Correct 23 ms 6308 KB Output is correct
12 Correct 288 ms 6308 KB Output is correct
13 Correct 213 ms 6308 KB Output is correct
14 Correct 251 ms 6308 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 5564 KB Output is correct
2 Correct 561 ms 5700 KB Output is correct
3 Correct 623 ms 5716 KB Output is correct
4 Correct 578 ms 5732 KB Output is correct
5 Correct 225 ms 5732 KB Output is correct
6 Correct 497 ms 5732 KB Output is correct
7 Correct 165 ms 5732 KB Output is correct
8 Correct 298 ms 5732 KB Output is correct
9 Correct 517 ms 6108 KB Output is correct
10 Correct 537 ms 6308 KB Output is correct
11 Correct 23 ms 6308 KB Output is correct
12 Correct 288 ms 6308 KB Output is correct
13 Correct 213 ms 6308 KB Output is correct
14 Correct 251 ms 6308 KB Output is correct
15 Correct 645 ms 6492 KB Output is correct
16 Correct 489 ms 6492 KB Output is correct
17 Correct 607 ms 6868 KB Output is correct
18 Correct 540 ms 6868 KB Output is correct
19 Correct 573 ms 7020 KB Output is correct
20 Correct 559 ms 7248 KB Output is correct
21 Correct 553 ms 7248 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 2 ms 756 KB Output is correct
3 Correct 3 ms 816 KB Output is correct
4 Correct 2 ms 816 KB Output is correct
5 Correct 2 ms 836 KB Output is correct
6 Correct 2 ms 836 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 3 ms 956 KB Output is correct
9 Correct 3 ms 1008 KB Output is correct
10 Correct 3 ms 1128 KB Output is correct
11 Correct 3 ms 1128 KB Output is correct
12 Correct 4 ms 1128 KB Output is correct
13 Correct 21 ms 1868 KB Output is correct
14 Correct 16 ms 2004 KB Output is correct
15 Correct 13 ms 2004 KB Output is correct
16 Correct 21 ms 2080 KB Output is correct
17 Correct 29 ms 2080 KB Output is correct
18 Correct 18 ms 2084 KB Output is correct
19 Correct 528 ms 5564 KB Output is correct
20 Correct 561 ms 5700 KB Output is correct
21 Correct 623 ms 5716 KB Output is correct
22 Correct 578 ms 5732 KB Output is correct
23 Correct 225 ms 5732 KB Output is correct
24 Correct 497 ms 5732 KB Output is correct
25 Correct 165 ms 5732 KB Output is correct
26 Correct 298 ms 5732 KB Output is correct
27 Correct 517 ms 6108 KB Output is correct
28 Correct 537 ms 6308 KB Output is correct
29 Correct 23 ms 6308 KB Output is correct
30 Correct 288 ms 6308 KB Output is correct
31 Correct 213 ms 6308 KB Output is correct
32 Correct 251 ms 6308 KB Output is correct
33 Correct 645 ms 6492 KB Output is correct
34 Correct 489 ms 6492 KB Output is correct
35 Correct 607 ms 6868 KB Output is correct
36 Correct 540 ms 6868 KB Output is correct
37 Correct 573 ms 7020 KB Output is correct
38 Correct 559 ms 7248 KB Output is correct
39 Correct 553 ms 7248 KB Output is correct
40 Correct 605 ms 9032 KB Output is correct
41 Correct 24 ms 9032 KB Output is correct
42 Correct 596 ms 9032 KB Output is correct
43 Correct 540 ms 9032 KB Output is correct
44 Correct 520 ms 9032 KB Output is correct
45 Correct 680 ms 15668 KB Output is correct
46 Correct 31 ms 15668 KB Output is correct
47 Correct 670 ms 15952 KB Output is correct
48 Correct 628 ms 15952 KB Output is correct
49 Correct 576 ms 15952 KB Output is correct