Submission #1213465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213465		andreim	Grudanje (COCI19_grudanje)	C++20	63 / 70	24 ms	1352 KiB

grudanje

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

struct Intervalle {
    int deb, fin;
};

bool comp(const Intervalle& a, const Intervalle& b)
{
    if (a.deb == b.deb)
        return a.fin < b.fin;
    return a.deb < b.deb;
}

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    string mot;
    cin >> mot;
    int N = mot.length();
    int nbRequetes;
    cin >> nbRequetes;
    vector<Intervalle> requetes(nbRequetes);
    for (int _ = 0; _ < nbRequetes; _++)
    {
        cin >> requetes[_].deb >> requetes[_].fin;
        requetes[_].deb--; requetes[_].fin--;
    }

    sort(requetes.begin(), requetes.end(), comp);

    /* cout << "MES INTER :\n";
    for (auto inter : requetes)
        cout << inter.deb << " " << inter.fin << "\n"; */

    vector<Intervalle> disjoints;
    disjoints.push_back(requetes[0]);
    for (int i = 1; i < (int)requetes.size(); i++)
    {
        if (requetes[i].deb > disjoints[(int)disjoints.size() - 1].fin)
            disjoints.push_back(requetes[i]);
        else
            disjoints[(int)disjoints.size() - 1].fin = max(disjoints[(int)disjoints.size() - 1].fin, requetes[i].fin);
    }

    /* cout << "MES INTER :\n";
    for (auto inter : disjoints)
        cout << inter.deb << " " << inter.fin << "\n"; */

    vector<map<char, int>> occ((int)disjoints.size());
    vector<int> nbMotsAChanger((int)disjoints.size());
    for (int j = 0; j < (int)disjoints.size(); j++)
    {
        auto inter = disjoints[j];
        for (int i = inter.deb; i <= inter.fin; i++)
            occ[j][mot[i]]++;
        for (auto el : occ[j])
            if (el.second > 1)
                nbMotsAChanger[j]++;
    }

    /* cout << "MON MOT : " << mot << "\n";
    for (int j = 0; j < (int)disjoints.size(); j++)
    {
        auto inter = disjoints[j];
        cout << "JE REGARDE L'INTERVALLE : " << inter.deb << " et " << inter.fin << "\n";
        cout << "VOICI LES OCCURENCES DES MOTS DEDANS :\n";
        for (auto el : occ[j])
            cout << el.first << " : " << el.second << "\n";
        cout << "NB MOTS A CHANGER : " << nbMotsAChanger[j] << "\n";
    } */

    bool valide = true;
    for (int z = 0; z < (int)disjoints.size(); z++)
        if (nbMotsAChanger[z] != 0)
            valide = false;
    if (valide)
    {
        cout << "0\n";
        return 0;
    }

    for (int i = 0; i < N; i++)
    {
        int iChange;
        cin >> iChange;
        iChange--;
        
        bool valide2 = true;
        for (int z = 0; z < (int)disjoints.size(); z++)
        {
            // cout << "je suis dans l'intervalle " << disjoints[z].deb << " - " << disjoints[z].fin << " avec iChange " << iChange << "\n";
            auto inter = disjoints[z];
            if (iChange >= inter.deb && iChange <= inter.fin)
            {
                if (occ[z][mot[iChange]] == 2)
                    nbMotsAChanger[z]--;
                occ[z][mot[iChange]]--;
                // cout << "J'ai retiré une occurence de " << mot[iChange] << "\n";
            }

            if (nbMotsAChanger[z] > 0)
                valide2 = false;
        }

        if (valide2)
        {
            cout << i + 1 << "\n";
            return 0;
        }
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7