Submission #1213472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213472		andreim	Grudanje (COCI19_grudanje)	C++20	63 / 70	26 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);

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

        vector<map<char, int>> occ((int)requetes.size());
        vector<int> nbMotsAChanger((int)requetes.size());
        for (int j = 0; j < (int)requetes.size(); j++)
        {
            auto inter = requetes[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)requetes.size(); j++)
        {
            auto inter = requetes[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)requetes.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)requetes.size(); z++)
            {
                // cout << "je suis dans l'intervalle " << requetes[z].deb << " - " << requetes[z].fin << " avec iChange " << iChange << "\n";
                auto inter = requetes[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;
            }
        }
    }
    else
    {
        /* 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