Submission #1059871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059871		Piokemon	Lottery (CEOI18_lot)	C++17	65 / 100	408 ms	16732 KiB

lot

#include <iostream>
#include <map>
using namespace std;
typedef long long int ll;

constexpr int N = 2000;
constexpr int N2 = 1e4;
short int odp[N+9][N+9];
int a[N2+9];
pair<ll,ll> mod = {2e9+323,2e9+11};
pair<ll,ll> byl[N2+9];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,l,q,pyt;
    cin >> n >> l;
    for (int x=1;x<=n;x++) cin >> a[x];
    cin >> q;
    cin >> pyt;
    if (q==1 && pyt==0){
        pair<ll,ll> maks={1,1};
        pair<ll,ll> ter={0,0};
        ll p=1e9+1;
        map<pair<ll,ll>,int> cnt;
        for (int x=1;x<l;x++)maks={(maks.first*p)%mod.first,(maks.second*p)%mod.second};
        for (int x=1;x<=l;x++)ter={((ter.first*p)+a[x])%mod.first,((ter.second*p)+a[x])%mod.second};
        cnt[ter]++;
        byl[1]=ter;
        for (int x=2;x<=n-l+1;x++){
            ter.first = (ter.first-maks.first*a[x-1]+mod.first*mod.first)%mod.first;
            ter.second = (ter.second-maks.second*a[x-1]+mod.second*mod.second)%mod.second;
            ter={((ter.first*p)+a[x+l-1])%mod.first,((ter.second*p)+a[x+l-1])%mod.second};
            cnt[ter]++;
            byl[x]=ter;
        }
        for (int x=1;x<=n-l+1;x++) cout << cnt[byl[x]]-1 << ' ';
        cout << '\n';
        return 0;
    }
    int dist;
    for (int x=1;x<=n-l;x++){
        for (int y=x+1;y<=n-l+1;y++){
            dist=0;
            for (int z=0;z<l;z++)dist+=a[x+z]!=a[y+z];
            odp[x][dist]++;
            odp[y][dist]++;
        }
    }
    for (int x=1;x<=n;x++){
        for (int k=1;k<=n;k++)odp[x][k]=odp[x][k]+odp[x][k-1];
    }
    while(q--){
        for (int x=1;x<=n-l+1;x++) cout << odp[x][pyt] << ' ';
        cout << '\n';
        cin >> pyt;
    }
    return 0;
}

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