Submission #891053

#	Time	Username	Problem	Language	Result	Execution time	Memory
891053		kokoxuya	Martian DNA (BOI18_dna)	C++14	100 / 100	91 ms	142420 KiB

dna

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

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int N, K, R, temp1,temp2; 
    cin >> N >> K >> R;
    vector<int>strand(N);
    vector<int>requirements(K);
    vector<queue<int>>positions(K);
    vector<int>nummet(K);
    int reqmet = K;
    fill(requirements.begin(),requirements.end(),0);
    fill(nummet.begin(),nummet.end(),0);

    for (int a = 0; a < N; a++)
    {
        cin >> strand[a];
    }
    for (int a = 0; a < R; a++)
    {
        cin >> temp1 >> temp2; //type, need
        requirements[temp1] = temp2;
        reqmet--;
    }
    vector<int>requirementscopy(requirements.begin(),requirements.end());
    queue<pair<int,int>>tracker; //position, dna type
    /*cout << "outputting requirements:\n";
    for (int a = 0 ; a < K; a++)
    {
        cout << requirements[a] << " ";
    }
    cout << "\n";*/

    if (R == 0) //no requirements, sui bian ni! :D
    {
        cout << 0;
        return 0;
    }

    int currdna, ans = LLONG_MAX;
    for (int a = 0; a < N; a++)
    {
        currdna = strand[a];
        if (!requirementscopy[currdna]) //if you dont need that dna
        {
            continue;
        }
        if (requirements[currdna] == 1) //just hit the needed goal!
        {
            //cout << "met requirement for " << currdna << " at " << a << "\n";
            reqmet++; 
        }
        requirements[currdna]--;
        positions[currdna].push(a); //if you go over the required amount, cut out the first one
        nummet[currdna] ++;
        tracker.push(make_pair(a,currdna));
        if (nummet[currdna] > requirementscopy[currdna]) //youve met mroe than u need
        {
            positions[currdna].pop();
        }
        
        //checking :)

        if (reqmet == K)
        {
            while (tracker.front().first != (positions[tracker.front().second].front()))
            {
                tracker.pop();
            }
            ans = min(ans, (a - tracker.front().first + 1));
        }
    }

    /*for (int a = 0 ; a < K; a++)
    {
        cout << a << " : \n";
        while(!positions[a].empty())
        {
            cout << positions[a].front() << " ";
            positions[a].pop();
        }
        cout << "\n";
    }
    cout << "\n";*/

    if (ans == LLONG_MAX)
    {
        cout << "impossible";
    }
    else
    {
        cout << ans;
    }
}

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32