oj.uz

Submission #1095348

# Submission time Handle Problem Language Result Execution time Memory
1095348 2024-10-02T01:41:26 Z SoMotThanhXuan Lottery (CEOI18_lot) C++17
25 / 100
 4 ms 2908 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e4 + 5;
int N, L, a[maxN], k[maxN], Q, M;
namespace subtask1{
    bool check(){
        return N <= 300;
    }
    int res[303][303];

    void solve(){
        for(int i = 1; i <= M; ++i){
            for(int j = i + 1; j <= M; ++j){
                int cnt = 0;
                for(int x = 0; x < L; ++x){
                     if(a[i + x] != a[j + x])++cnt;
                }
                res[i][cnt]++;
                res[j][cnt]++;
            }
        }
        for(int i = 1; i <= M; ++i)for(int j = 1; j <= L; ++j)res[i][j] += res[i][j - 1];
        for(int i = 1; i <= Q; ++i){
            for(int j = 1; j <= M; ++j)cout << res[j][k[i]] << ' ';cout << "\n";
        }
    }
}
namespace subtask2{
    bool check(){
        return N <= 2000;
    }
    int diff[2001][2001];// doan [i va
    int res[2001][2001];
    void solve(){
        for(int i = 1; i <= M; ++i){
            for(int x = 1; x < L; ++x){
                if(a[i] != a[i + x]){
                    diff[max(1, i + 1 - x)][x]++;
                    diff[i + 1][x]--;
                }
            }
        }
    }
}
namespace subtask3{
    bool check(){
        return Q == 1 && k[1] == 0;
    }
    int comp[maxN];
    const int BASE = 10000;
    const int mod = 1e9 + 9;
    const long long MS = 1ll * mod * mod;
    #define hash __hash
    int hash[maxN], power[maxN];
    int getHash(int i, int j){
        return (hash[j] - 1ll * hash[i - 1] * power[j - i + 1] + MS) % mod;
    }
    pair<int, int> d[maxN];
    int cnt[maxN], res[maxN];
    void solve(){
        for(int i = 1; i <= N; ++i)comp[i] = a[i];
        sort(comp + 1, comp + 1 + N);
        for(int i = 1; i <= N; ++i){
            a[i] = lower_bound(comp + 1, comp + 1 + N, a[i]) - comp;
        }
        power[0] = 1;
        for(int i = 1; i <= N; ++i){
            power[i] = 1ll * power[i - 1] * BASE % mod;
            hash[i] = (1ll * hash[i - 1] * BASE + a[i]) % mod;
        }
        for(int i = 1; i <= M; ++i){
            d[i] = {getHash(i, i + L - 1), i};
            comp[i] = d[i].first;
        }
        sort(d + 1, d + 1 + M);
        sort(comp + 1, comp + 1 + M);
        for(int i = 1; i <= M; ++i){
            d[i].first = lower_bound(comp + 1, comp + 1 + M, d[i].first) - comp;
            cnt[d[i].first]++;
        }
        for(int i = 1; i <= M; ++i)res[d[i].second] = cnt[d[i].first];
        for(int i = 1; i <= M; ++i)cout << --res[i] << ' ';
    }
}
int main(){
//    freopen("lot.inp", "r", stdin);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N >> L;
    M = N - L + 1;
    for(int i = 1; i <= N; ++i)cin >> a[i];
    cin >> Q;
    for(int i = 1; i <= Q; ++i){
        cin >> k[i];
    }
    if(subtask1 :: check()) return subtask1 :: solve(), 0;
    if(subtask3 :: check()) return subtask3 :: solve(), 0;
    return 0;
}

Compilation message

lot.cpp: In function 'void subtask1::solve()':
lot.cpp:25:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   25 |             for(int j = 1; j <= M; ++j)cout << res[j][k[i]] << ' ';cout << "\n";
      |             ^~~
lot.cpp:25:68: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   25 |             for(int j = 1; j <= M; ++j)cout << res[j][k[i]] << ' ';cout << "\n";
      |                                                                    ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 656 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 656 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 3 ms 2716 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 3 ms 2656 KB Output is correct
7 Correct 2 ms 2632 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 3 ms 2908 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 3 ms 2780 KB Output is correct
13 Incorrect 3 ms 2628 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 3 ms 2716 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 3 ms 2656 KB Output is correct
7 Correct 2 ms 2632 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 3 ms 2908 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 3 ms 2780 KB Output is correct
13 Incorrect 3 ms 2628 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 656 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -