제출 #656354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
656354		perchuts	Lottery (CEOI18_lot)	C++17	80 / 100	515 ms	8140 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<ii>qu(q);

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

    sort(all(qu));

    int i = 0;

    for(int j=0;j<q;++j)
        while(i!=qu[j].first)++i, where[i] = j;
    
    while(i!=l)++i, where[i] = q+1;

    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<q;++j)
            ans[i][j] += ans[i][j-1];
    
    sort(all(qu), [&](ii x,ii y){return x.second<y.second;});

    for(auto [a,b]:qu)
        for(int i=1;i<=n-l+1;++i)cout<<ans[i][where[a]]<<" \n"[i==n-l+1];
    
}

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