Submission #266984

#	Time	Username	Problem	Language	Result	Execution time	Memory
266984		etienne	Lottery (CEOI18_lot)	C++14	0 / 100	486 ms	4352 KiB

lot

#include <bits/stdc++.h>
using namespace std;

const int MAX_VAL=1e4,MAX_QUEST=1e2;

int tirage[MAX_VAL],
    tab_cumu[MAX_VAL][MAX_QUEST],
    req_sup[MAX_VAL],
    questions[MAX_QUEST];

vector<pair<int,int>> quest_dep;

int nbVal,long_inter, nbQuest,verif0;

void input() {
    cin >> nbVal >> long_inter;
    for (int iVal=0;iVal<nbVal;iVal++) {
        cin >> tirage[iVal];
    }
    cin >> nbQuest;
    for (int iQuest=0;iQuest<nbQuest;iQuest++) {
        cin >> questions[iQuest];
        if (questions[iQuest]==0)
            verif0=1;
        quest_dep.push_back(make_pair(questions[iQuest],iQuest));
    }
    sort(quest_dep.begin(),quest_dep.end());
}

int main() {
    ios::sync_with_stdio(false);
    
    input();

    for (int iQuest=0;iQuest<nbQuest;iQuest++) {
        req_sup[quest_dep[iQuest].first]=quest_dep[iQuest].first;
    }
    req_sup[nbVal-1]=nbVal-1;
    for (int iVal=nbVal-2;iVal>=0;iVal--) {
        if (req_sup[iVal]==0) 
            req_sup[iVal]=req_sup[iVal+1];
    }
    if (verif0==1)
        req_sup[0]=0;

    int pb,nbInter=nbVal-long_inter+1;
    for (int dist=1;dist<nbInter;dist++) { 
        pb=0;
        for (int iVal=0;iVal<long_inter-1;iVal++) {
            if (tirage[iVal]!=tirage[iVal+dist])
                pb++;
        }
        for (int iDeb=0;iDeb<nbInter-dist;iDeb++) {
            if (tirage[iDeb+long_inter-1]!=tirage[iDeb+dist+long_inter-1])
                pb++;
            //cout << pb << " ";
            tab_cumu[iDeb][req_sup[pb]]++;
            tab_cumu[iDeb+dist][req_sup[pb]]++;
            if (tirage[iDeb]!=tirage[iDeb+dist])
                pb--;

        }
        //cout << endl;
    }
    for (int iDeb=0;iDeb<nbInter;iDeb++) {
        //cout << req_sup[iDeb] << " ";
        for (int iQuest=1;iQuest<nbQuest;iQuest++) {
            tab_cumu[iDeb][iQuest]+=tab_cumu[iDeb][iQuest-1];
        }
    }
    //cout << endl;

    for (int iQuest=0;iQuest<nbQuest;iQuest++) {
        for (int iDeb=0;iDeb<nbInter;iDeb++) {
            cout << tab_cumu[iDeb][questions[iQuest]] << " ";
        }
        cout << endl;
        //cout << pos_quest[questions[iQuest]];
    }
    return 0;
}

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