Submission #1054462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054462		alexander707070	Painting Walls (APIO20_paint)	C++14	0 / 100	2 ms	7260 KiB

paint

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

#define MAXN 100007
using namespace std;

int n,m,k,ans;
int c[MAXN];
unordered_set<int> cols[MAXN];

bool can[MAXN];
int to[2][MAXN];
int best[MAXN],pref[MAXN];

int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector< vector<int> > B) {
    n=N; m=M; k=K;

    for(int i=1;i<=n;i++){
        c[i]=C[i-1];
    }

    for(int i=1;i<=m;i++){
        for(int s:B[i-1])cols[i].insert(s);
    }

    for(int i=n;i>=1;i--){
        for(int f=1;f<=m;f++){
            if(cols[f].find(c[i])!=cols[f].end())can[f]=true;

            if(!can[f])to[i%2][f]=0;
            else{
                if(f<m)to[i%2][f]=to[1-i%2][f+1]+1;
                else to[i%2][f]=to[1-i%2][1]+1;
            }

            if(to[i%2][f]>=m)best[i]=max(best[i],i+m);
        }
    }

    for(int i=1;i<=n;i++){
        pref[i]=max(pref[i-1],best[i]);
    }

    int pos=1;
    while(pos<=n){
        if(pref[pos]<=pos)return -1;

        pos=pref[pos];
        ans++;
    }

    return ans;
}

/*
int main(){
    //cout<<minimumInstructions(8, 3, 5, {3, 3, 1, 3, 4, 4, 2, 2}, {3, 2, 2}, {{0, 1, 2}, {2, 3}, {3, 4}});
    cout<<minimumInstructions(5, 4, 4, {1, 0, 1, 2, 2}, {2, 1, 1, 1}, {{0, 1}, {1}, {2}, {3}});


    return 0;
}
*/

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