Submission #429758

#	Time	Username	Problem	Language	Result	Execution time	Memory
429758		Peti	Painting Walls (APIO20_paint)	C++14	100 / 100	465 ms	15388 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

int minimumInstructions(int n, int m, int k, std::vector<int> c, std::vector<int> a, std::vector<std::vector<int>> b) {

    vector<vector<int>> inds(k);
    for(int i = 0; i < m; i++)
        for(int x : b[i])
            inds[x].push_back(i);

    for(int i = 0; i < k; i++)
        reverse(inds[i].begin(), inds[i].end());

    vector<pair<int, int>> last(m, make_pair(-2, 0));
    vector<int> kezd(n, 0), veg(n, 0);
    for(int i = 0; i < n; i++){
        for(int x : inds[c[i]]){
            if(x > 0 && last[x-1].first == i-1)
                last[x] = make_pair(i, last[x-1].second+1);
            else
                last[x] = make_pair(i, 1);
        }
        /*for(auto p : last)
            cout<<"("<<p.first<<", "<<p.second<<") ";
        cout<<"\n";*/
        if(last[m-1].first == i)
            veg[i] = last[m-1].second;
    }

    for(int i = 0; i < k; i++)
        reverse(inds[i].begin(), inds[i].end());

    last.assign(m, make_pair(n+1, 0));
    for(int i = n-1; i >= 0; i--){
        for(int x : inds[c[i]]){
            if(x < n-1 && last[x+1].first == i+1)
                last[x] = make_pair(i, last[x+1].second+1);
            else
                last[x] = make_pair(i, 1);
        }
        if(last[0].first == i)
            kezd[i] = last[0].second;
    }

    /*cout<<"veg: ";
    for(int x : veg)
        cout<<x<<" ";
    cout<<"\n";
    cout<<"kezd: ";
    for(int x : kezd)
        cout<<x<<" ";
    cout<<"\n";*/

    vector<pair<int, int>> v;
    for(int i = 0; i < n; i++){
        if(i < n-1 && veg[i] + kezd[i+1] >= m){
            v.emplace_back(i-veg[i]+1, i + kezd[i+1] - m + 1);
        } else if(veg[i] == m)
            v.emplace_back(i-veg[i]+1, i-veg[i]+1);
    }

    /*cout<<"ints:\n";
    for(auto p : v)
        cout<<p.first<<" "<<p.second<<"\n";*/

    sort(v.begin(), v.end());

    int x = 0, e = 0, legn = -m-1, meg = 0;
    while(e < n){
        while(x < (int)v.size() && v[x].first <= e)
            legn = max(legn, v[x++].second);
        if(legn+m <= e)
            return -1;
        e = min(e+m, legn+m);
        meg++;
    }

    return meg;
}

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37