제출 #1246482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246482		Jovica	Lottery (CEOI18_lot)	C++20	100 / 100	1174 ms	8204 KiB

lot

#include <bits/stdc++.h>

using namespace std;
map<int,int> prevod;

void kompres(set<int> s)
{
    int p = 0;
    for (auto a: s){
        prevod[a] = p;
        p++;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,l;
    cin>>n>>l;
    vector<int> v(n);
    for (int i=0;i<n;i++) cin>>v[i];

    int q;
    cin>>q;
    set<int> s;
    vector<int> redosled;
    int kolku_razlicni = 0;
    for (int i=0;i<q;i++)
    {
        int a;
        cin>>a;
        if (s.count(a) == 0) kolku_razlicni++;
        s.insert(a);
        redosled.push_back(a);
    }

    kompres(s);

    vector<vector<int> > ans(kolku_razlicni);
    for (int i=0;i<kolku_razlicni;i++) ans[i].resize(n-l+1,0);

    /*cout<<" ans: ";
    for (int i=0;i<ans.size();i++)
    {
        for (auto a: ans[i]) cout<<a<<" ";
        cout<<endl;
    }
    cout<<"-"<<endl;*/
    s.insert(1e5);

    for (int d = 1;d+l<=n;d++)
    {
        int raz = 0;
        for (int i=0;i<l;i++) if (v[i] != v[i+d]) raz++;

        for (int p1=0,p2=d;p2+l<=n;p1++,p2++)
        {
            if (p1>0)
            {
                if (v[p1-1] != v[p2-1]) raz--;
                if (v[p1+l-1] != v[p2+l-1]) raz++;
            }
            //cout<<"od "<<p1<<" do "<<p1+l-1<<" i od "<<p2<<" do "<<p2+l-1<<" ima "<<raz<<" razliki\n";

            int kade = *s.lower_bound(raz);
            //cout<<"kade = "<<kade<<endl;
            if (kade == 1e5) continue;
            kade = prevod[kade];
            ans[kade][p1] ++;ans[kade][p2] ++;
        }
    }

    for (int i=0;i+1<ans.size();i++)
    {
        for (int j=0;j<ans[i].size();j++) ans[i+1][j] += ans[i][j];
    }

    for (auto a: redosled)
    {
        int p = prevod[a];
        for (auto x: ans[p]) cout<<x<<" ";
        cout<<"\n";
    }

    return 0;
}

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