Submission #656356

#	Time	Username	Problem	Language	Result	Execution time	Memory
656356		perchuts	Lottery (CEOI18_lot)	C++17	100 / 100	486 ms	8252 KiB

lot

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e4+1;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

int a[maxn], where[maxn], ans[maxn][101], resp[100];

int main(){_
    int n,l;cin>>n>>l;

    for(int i=1;i<=n;++i)cin>>a[i];    

    int q;cin>>q;

    vector<int>qu(q), ord;

    for(int i=0;i<q;++i)cin>>qu[i], ord.pb(qu[i]);

    sort(all(ord));

    ord.erase(unique(all(ord)),end(ord));

    int i = 0;

    for(int j=0;j<sz(ord);++j)
        while(i!=ord[j])++i, where[i] = j;
    
    while(i!=l)++i, where[i] = q;

    for(int i=1;i<=n-l;++i){//distance from two strings
        int x = 1, y = 1 + i, cur = 0;
        for(int j=0;j<l;++j)cur += (a[j+1]!=a[i+j+1]);
        ans[x++][where[cur]]++, ans[y++][where[cur]]++;
        while(y+l-1<=n){
            cur += (a[x+l-1]!=a[y+l-1])-(a[x-1]!=a[y-1]);
            ans[x++][where[cur]]++, ans[y++][where[cur]]++;
        }
    }

    for(int i=1;i<=n-l+1;++i)
        for(int j=1;j<sz(ord);++j)
            ans[i][j] += ans[i][j-1];
    
    for(auto x:qu)
        for(int i=1;i<=n-l+1;++i)cout<<ans[i][where[x]]<<" \n"[i==n-l+1];
    
}

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