Submission #556126

#	Time	Username	Problem	Language	Result	Execution time	Memory
556126		aryan12	Painting Walls (APIO20_paint)	C++17	40 / 100	1583 ms	136384 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

int minimumInstructions(int N, int M, int K, vector<int> colors, vector<int> num, vector<vector<int> > B) {
    /*
    Idea:
    1. Check for all contractors who like to color colors[N - 1];
    2. Traverse backwards, and update values of contractors
    3. suffix[contractor X] = Y means that X paints Y, X + 1 paints Y + 1 and so on.
    */

    auto begin = std::chrono::high_resolution_clock::now();

    set<pair<int, int> > Matches; //contractor, color;

    for(int i = 0; i < M; i++) {
        for(int j = 0; j < num[i]; j++) {
            Matches.insert(make_pair(i, B[i][j]));
        }
    }

    vector<int> LastColorLike, FirstColorLike;
    for(int i = 0; i < N; i++) {
        if(Matches.count(make_pair(M - 1, colors[i]))) {
            LastColorLike.push_back(i);
        }
        if(Matches.count(make_pair(0, colors[i]))) {
            FirstColorLike.push_back(i);
        }
    }

    //auto end = std::chrono::high_resolution_clock::now();
    //auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    //assert((elapsed.count() * 1e-9) < 1500);

    //LastColorLike stuff ------------------------------------------------------------



    set<int> suffixLiking[M];
    //set<int> AlreadyTaken[M];
    for(int colorIdx: LastColorLike) {
        //cout << "colorIdx = " << colorIdx << "\n";
        int curContractor = M - 1;
        if(!suffixLiking[curContractor].count(colorIdx)) {
            suffixLiking[curContractor].insert(colorIdx);
            //AlreadyTaken[curContractor].insert(colorIdx);
        }
        else {
            break;
        }
        for(int i = curContractor - 1; i >= 0; i--) {
            colorIdx--;
            //cout << "i = " << i << ", colorIdx = " << colorIdx << "\n";
            if(colorIdx < 0) {
                break;
            }
            if(Matches.count({i, colors[colorIdx]})) {
                if(!suffixLiking[i].count(colorIdx)) {
                    //AlreadyTaken[i].insert(colorIdx);
                    suffixLiking[i].insert(colorIdx);
                }
                else {
                    break;
                }
            }
            else {
                break;
            }
        }
    }

    //auto end = std::chrono::high_resolution_clock::now();
    //auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    //assert((elapsed.count() * 1e-9) < 1500);

    /*for(int i = 0; i < M; i++) {
        for(auto j: suffixLiking[i]) {
            cout << "i = " << i << ", suffix = " << j << "\n";
        }
        cout << "\n\n";
    }*/

    //--------------------------------------------------------------------------------

    //FirstColorLike stuff -----------------------------------------------------------

    set<int> prefixLiking[M];
    for(int colorIdx: FirstColorLike) {
        int curContractor = 0;
        if(!prefixLiking[curContractor].count(colorIdx)) {
            prefixLiking[curContractor].insert(colorIdx);
        }
        else {
            break;
        }
        for(int i = 1; i < M; i++) {
            colorIdx++;
            if(colorIdx >= N) {
                break;
            }
            if(Matches.count({i, colors[colorIdx]})) {
                if(!prefixLiking[i].count(colorIdx)) {
                    prefixLiking[i].insert(colorIdx);
                }
                else {
                    break;
                }
            }
            else {
                break;
            }
        }
    }

    //auto end = std::chrono::high_resolution_clock::now();
    //auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    //assert((elapsed.count() * 1e-9) < 1500);

    /*for(int i = 0; i < M; i++) {
        for(auto j: prefixLiking[i]) {
            cout << "i = " << i << ", prefix = " << j << "\n";
        }
        cout << "\n\n";
    }*/

    //--------------------------------------------------------------------------------

    set<int> specificPrefix[N], specificSuffix[N];
    for(int i = 0; i < M; i++) {
        for(auto j: prefixLiking[i]) {
            specificPrefix[j].insert(i);
        }
        for(auto j: suffixLiking[i]) {
            specificSuffix[j].insert(i);
        }
    }

    int furthestTaken = 0, ans = 0;
    set<int> alreadyVisited;
    while(furthestTaken != N) {
        //cout << "furthestTaken = " << furthestTaken << "\n";
        int curColorIdx = furthestTaken;
        while(curColorIdx >= 0 && curColorIdx >= furthestTaken - M) {
            //cout << "curColorIdx = " << curColorIdx << "\n";
            if(alreadyVisited.count(curColorIdx) || N - curColorIdx < M) {
                curColorIdx--;
                continue;
            }
            //cout << "continued\n";
            int f = 0;
            alreadyVisited.insert(curColorIdx);
            for(auto i: specificSuffix[curColorIdx]) {
                int curIdx = i;
                if(curIdx == 0) {
                    f = 1;
                    furthestTaken = curColorIdx + M;
                    ans++;
                    break;
                }
                int prefixIdx = curIdx - 1;
                int added = curColorIdx + M - 1;
                if(specificPrefix[added].count(prefixIdx)) {
                    f = 1;
                    furthestTaken = curColorIdx + M;
                    ans++;
                    break;
                }
            }
            //cout << "f = " << f << "\n";
            if(f == 1) {
                break;
            }
            curColorIdx--;
        }
        if(curColorIdx < 0 || curColorIdx < furthestTaken - M) {
            ans = -1;
            break;
        }
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    assert((elapsed.count() * 1e-9) < 1500);
    return ans;
}


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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() {
    
}

int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}*/

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