Submission #884917

#	Time	Username	Problem	Language	Result	Execution time	Memory
884917		devvops	Lottery (CEOI18_lot)	C++17	65 / 100	265 ms	65536 KiB

lot

#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <climits>
#include <random>
using namespace std;
  
#define ll long long
#define pb push_back
#define ull unsigned long long
#define F first
#define S second
#define all(v) v.begin(), v.end() 

const int mod = (int) 1e9 + 7;
const int P = 337;

int a[10001];
int n, l, q;

void sub3(){
    ll hsh[n + 1];
    ll p[l + 1];
    p[0] = 1;
    for(int i = 1; i <= l; i++){
        p[i] = (p[i - 1] * (P + 0LL)) % mod;
    }
    for(int i = 1; i <= n; i++){
        hsh[i] = (hsh[i - 1] * (P + 0LL)) % mod;
        hsh[i] += a[i];
        if(hsh[i] >= mod) hsh[i] -= mod;
    }
    for(int l1 = 1; l1 <= n - l + 1; l1++){
        int r1 = l1 + l - 1;
        ll g1 = (hsh[l1 - 1] * p[r1 - l1 + 1]) % mod;
        g1 = hsh[r1] - g1;
        if(g1 < 0) g1 += mod;
        int ans = 0;
        for(int l2 = 1; l2 <= n - l + 1; l2++){
            if(l1 == l2) continue;
            int r2 = l2 + l - 1;
            ll g2 = (hsh[l2 - 1] * p[r2 - l2 + 1]) % mod;
            g2 = hsh[r2] - g2;
            if(g2 < 0) g2 += mod;
            if(g1 == g2) ans++;
        }
        cout << ans << " ";
    }
}

void sub2(){
    int pref[n + 1][n + 1];
    int dp[n + 1][n + 1];
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            pref[i][j] = 0;
            dp[i][j] = 0;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            pref[i][j] = pref[i - 1][j - 1] + (a[i] == a[j]);
        }
    }
    for(int l1 = 1; l1 <= n - l + 1; l1++){
        int r1 = l1 + l - 1;
        for(int l2 = 1; l2 <= n - l + 1; l2++){
            int r2 = l2 + l - 1;
            int k = (r1 - l1 + 1) - (pref[r1][r2] - pref[l1 - 1][l2 - 1]);
            dp[l1][k]++;
        }
    }
    for(int i = 1; i <= n; i++){
        int p = 0;
        for(int j = 0; j <= l; j++){
            dp[i][j] += p;
            p = dp[i][j];
        }
    }
    while(q--){
        int k;
        cin >> k;
        for(int i = 1; i <= n - l + 1; i++){
            cout << dp[i][k] - 1 << " ";
        }
        cout << '\n';
    }
}

void sub2_1(int k){
    int pref[n + 1][n + 1];
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            pref[i][j] = 0;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            pref[i][j] = pref[i - 1][j - 1] + (a[i] == a[j]);
        }
    }
    for(int l1 = 1; l1 <= n - l + 1; l1++){
        int r1 = l1 + l - 1;
        int cnt = 0, p = 0;
        for(int l2 = 1; l2 <= n - l + 1; l2++){
            if(l1 == l2) continue;
            int r2 = l2 + l - 1;
            int x = (r1 - l1 + 1) - (pref[r1][r2] - pref[l1 - 1][l2 - 1]);
            if(x <= k){
                cnt++;
            }
        }
        cout << cnt << " ";
    }
}

void solve(){
    cin >> n >> l;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    cin >> q;
    if(q == 1 && n > 2000){
        int k;
        cin >> k;
        if(k == 0){
            sub3();
        }
        else{
            sub2_1(k);
        }   
    }
    else{
        sub2();
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int xach = 1;  
    //cin >> xach;
    while(xach--) solve();
}
/*
 *
*/

Compilation message (stderr)

lot.cpp: In function 'void sub2_1(int)':
lot.cpp:130:22: warning: unused variable 'p' [-Wunused-variable]
  130 |         int cnt = 0, p = 0;
      |                      ^

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20