oj.uz

Submission #827624

# Submission time Handle Problem Language Result Execution time Memory
827624 2023-08-16T15:24:15 Z Ronin13 Lottery (CEOI18_lot) C++17
35 / 100
 716 ms 588 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <bitset>
#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back

using namespace std;
const int nmax = 15001;

int ans[nmax];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int l; cin >> l;
    int a[n + 1];
    int b[n + 1];
    fill(b, b + n + 1, 0);
    for(int i  = 1; i <= n; i++){
        cin >> a[i];
    }
    int q; cin >> q;
    int cnt[n + 1][q];
    vector <int> vec;
    int k[q + 1];
    for(int i = 1; i <= q; i++){
        int x; cin >> x;
        k[i] = x;
        vec.pb(x);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for(int i = 1; i <= n; i++){
        for(int j =0; j < q; j++)
            cnt[i][j] = 0;
    }
    for(int d = 1; d <= n; d++){
        fill(b, b + n + 1, 0);
        for(int j = 1; j <= n - d; j++){
            b[j] = (a[j] != a[j + d]);
            b[j] += b[j - 1];
        }
        for(int i = 1; i <= n - l - d + 1; i++){
            int val = b[i + l - 1] - b[i - 1];
            int  x= lower_bound(vec.begin(), vec.end(), val) - vec.begin();
            if(x == vec.size()) continue;
            cnt[i][x]++;
        }
    }
    for(int d = 1; d <= n; d++){
        fill(b, b + n + 1, 0);
        for(int j = d + 1; j <= n; j++){
            b[j] = (a[j] != a[j - d]);
            b[j] += b[j - 1];
        }
        for(int i = d + 1; i <= n - l + 1; i++){
            int val = b[i + l - 1] - b[i - 1];
            int  x= lower_bound(vec.begin(), vec.end(), val) - vec.begin();
            if(x == vec.size()) continue;
            cnt[i][x]++;
        }
    }
    for(int j = 1; j < q; j++){
        for(int i = 1; i <= n; i++)
        cnt[i][j] += cnt[i][j - 1];
    }
    for(int j = 1; j <= q; j++){
        int ind = 0;
        for(int i = 0; i < q; i++)
            if(k[j] == vec[i]) ind = i;
        for(int i = 1; i <= n - l + 1; i++){
            cout << cnt[i][ind] << ' ';
        }
        cout << "\n";
    }
    return 0;
}

Compilation message

lot.cpp: In function 'int main()':
lot.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             if(x == vec.size()) continue;
      |                ~~^~~~~~~~~~~~~
lot.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             if(x == vec.size()) continue;
      |                ~~^~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 320 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 320 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 440 KB Output is correct
2 Correct 716 ms 440 KB Output is correct
3 Correct 559 ms 464 KB Output is correct
4 Correct 544 ms 512 KB Output is correct
5 Correct 339 ms 516 KB Output is correct
6 Correct 521 ms 460 KB Output is correct
7 Correct 308 ms 528 KB Output is correct
8 Correct 371 ms 520 KB Output is correct
9 Correct 532 ms 588 KB Output is correct
10 Correct 547 ms 508 KB Output is correct
11 Correct 37 ms 332 KB Output is correct
12 Correct 389 ms 496 KB Output is correct
13 Correct 359 ms 520 KB Output is correct
14 Correct 381 ms 516 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 440 KB Output is correct
2 Correct 716 ms 440 KB Output is correct
3 Correct 559 ms 464 KB Output is correct
4 Correct 544 ms 512 KB Output is correct
5 Correct 339 ms 516 KB Output is correct
6 Correct 521 ms 460 KB Output is correct
7 Correct 308 ms 528 KB Output is correct
8 Correct 371 ms 520 KB Output is correct
9 Correct 532 ms 588 KB Output is correct
10 Correct 547 ms 508 KB Output is correct
11 Correct 37 ms 332 KB Output is correct
12 Correct 389 ms 496 KB Output is correct
13 Correct 359 ms 520 KB Output is correct
14 Correct 381 ms 516 KB Output is correct
15 Correct 505 ms 436 KB Output is correct
16 Correct 534 ms 516 KB Output is correct
17 Correct 567 ms 520 KB Output is correct
18 Correct 552 ms 516 KB Output is correct
19 Correct 558 ms 516 KB Output is correct
20 Correct 548 ms 520 KB Output is correct
21 Correct 561 ms 520 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 320 KB Output isn't correct
12 Halted 0 ms 0 KB -