oj.uz

Submission #77940

# Submission time Handle Problem Language Result Execution time Memory
77940 2018-10-01T09:54:47 Z Saboon Lottery (CEOI18_lot) C++14
45 / 100
 633 ms 9892 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 = 2e3 + 10;

int n, l;

int a[maxn];

void compress () {
    vector <int> v;
    for (int i = 0; i < n; i++)
        v.PB (a[i]);
    sort (v.begin(), v.end());
    v.resize (unique (v.begin(), v.end()) - v.begin());
    for (int i = 0; i < n; i++)
        a[i] = lower_bound (v.begin(), v.end(), a[i]) - v.begin();
}

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 d[maxn][maxn];

int main () {
    ios_base::sync_with_stdio(false);
    cin >> n >> l;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n - l + 1; i++) {
        for (int j = i + 1; j < n - l + 1; j++) {
            int x = similar (i, j);
            d[i][x] ++;
            d[j][x] ++;
        }
    }
    for (int i = 0; i < n - l + 1; i++) {
        for (int j = 0; j <= l; j++) {
            d[i][j + 1] += d[i][j];
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < n - l + 1; j++)
            cout << d[j][k] << " ";
        cout << endl;
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 720 KB Output is correct
3 Correct 7 ms 816 KB Output is correct
4 Correct 2 ms 816 KB Output is correct
5 Correct 2 ms 816 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 5 ms 1264 KB Output is correct
9 Correct 4 ms 1332 KB Output is correct
10 Correct 4 ms 1784 KB Output is correct
11 Correct 5 ms 1804 KB Output is correct
12 Correct 4 ms 1804 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 720 KB Output is correct
3 Correct 7 ms 816 KB Output is correct
4 Correct 2 ms 816 KB Output is correct
5 Correct 2 ms 816 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 5 ms 1264 KB Output is correct
9 Correct 4 ms 1332 KB Output is correct
10 Correct 4 ms 1784 KB Output is correct
11 Correct 5 ms 1804 KB Output is correct
12 Correct 4 ms 1804 KB Output is correct
13 Correct 26 ms 8740 KB Output is correct
14 Correct 633 ms 9548 KB Output is correct
15 Correct 615 ms 9692 KB Output is correct
16 Correct 407 ms 9692 KB Output is correct
17 Correct 490 ms 9692 KB Output is correct
18 Correct 512 ms 9892 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 720 KB Output is correct
3 Correct 7 ms 816 KB Output is correct
4 Correct 2 ms 816 KB Output is correct
5 Correct 2 ms 816 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 5 ms 1264 KB Output is correct
9 Correct 4 ms 1332 KB Output is correct
10 Correct 4 ms 1784 KB Output is correct
11 Correct 5 ms 1804 KB Output is correct
12 Correct 4 ms 1804 KB Output is correct
13 Correct 26 ms 8740 KB Output is correct
14 Correct 633 ms 9548 KB Output is correct
15 Correct 615 ms 9692 KB Output is correct
16 Correct 407 ms 9692 KB Output is correct
17 Correct 490 ms 9692 KB Output is correct
18 Correct 512 ms 9892 KB Output is correct
19 Incorrect 3 ms 9892 KB Output isn't correct
20 Halted 0 ms 0 KB -