제출 #1213437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213437		andreim	Grudanje (COCI19_grudanje)	C++20	28 / 70	2096 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);

    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);
    }

    for (int i = 0; i <= N; i++)
    {
        if (i != 0)
        {
            int iChange;
            cin >> iChange;
            iChange--;
            mot[iChange] = '*';
        }

        int fini = 0;
        for (auto requete : disjoints)
        {
            map<int, bool> vus;
            bool valide = true;
            for (int j = requete.deb; j <= requete.fin; j++)
            {
                if (mot[j] != '*' && vus[mot[j]])
                {
                    valide = false;
                    break;
                }
                vus[mot[j]] = true;
            }

            if (valide)
                fini++;
        }

        if (fini == (int)disjoints.size())
        {
            cout << i << "\n";
            break;
        }
    }

    return 0;
}

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