oj.uz

Submission #362200

# Submission time Handle Problem Language Result Execution time Memory
362200 2021-02-02T03:40:14 Z sumit_kk10 Lottery (CEOI18_lot) C++14
45 / 100
 425 ms 65540 KB 
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
using namespace std;
const int MOD = 1e9 + 7;
const int N = 1e4;
vector<int> ans[N];
int n, k, q, a[N], dis;

void solve() {
    cin >> n >> k;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    for(int i = 0; i <= n - k; ++i) {
        for (int j = i + 1; j <= n - k; ++j) {
            if (i == j)
                continue;
            int diff = 0;
            for (int e = 0; e < k; ++e)
                if (a[i + e] != a[j + e])
                    ++diff;
            ans[i].push_back(diff);
            ans[j].push_back(diff);
        }
        sort(ans[i].begin(), ans[i].end());
    }
    cin >> q;
    while(q--){
        cin >> dis;
        for(int i = 0; i <= n - k; ++i){
            int low = 0, high = ans[i].size() - 1, ok = -1;
            while(low <= high){
                int mid = (low + high) / 2;
                if(ans[i][mid] <= dis){
                    ok = mid;
                    low = mid + 1;
                }
                else
                    high = mid - 1;
            }
            if(ok == -1) cout << "0 ";
            else cout << ok + 1 << " ";
        }
        cout << "\n";
    }
}

int main() {
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 4 ms 1144 KB Output is correct
11 Correct 5 ms 1144 KB Output is correct
12 Correct 3 ms 1132 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 4 ms 1144 KB Output is correct
11 Correct 5 ms 1144 KB Output is correct
12 Correct 3 ms 1132 KB Output is correct
13 Correct 112 ms 17004 KB Output is correct
14 Correct 400 ms 11532 KB Output is correct
15 Correct 425 ms 11628 KB Output is correct
16 Correct 331 ms 15132 KB Output is correct
17 Correct 353 ms 14316 KB Output is correct
18 Correct 362 ms 14316 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 278 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 278 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 4 ms 1144 KB Output is correct
11 Correct 5 ms 1144 KB Output is correct
12 Correct 3 ms 1132 KB Output is correct
13 Correct 112 ms 17004 KB Output is correct
14 Correct 400 ms 11532 KB Output is correct
15 Correct 425 ms 11628 KB Output is correct
16 Correct 331 ms 15132 KB Output is correct
17 Correct 353 ms 14316 KB Output is correct
18 Correct 362 ms 14316 KB Output is correct
19 Runtime error 278 ms 65540 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -