oj.uz

Submission #266984

# Submission time Handle Problem Language Result Execution time Memory
266984 2020-08-15T15:11:50 Z etienne Lottery (CEOI18_lot) C++14
0 / 100
 486 ms 4352 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 486 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 486 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -