제출 #1161599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161599		Aviansh	벽 칠하기 (APIO20_paint)	C++20	28 / 100	1595 ms	6584 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

int minimumInstructions(int n, int m, int k, vector<int> c,vector<int> a, vector<vector<int>> b) {
    vector<int>pos[k];
    for(int i = 0;i<m;i++){
        sort(b[i].begin(),b[i].end());
        for(int j : b[i]){
            pos[j].push_back(i);
        }
    }
    bool starts[n];
    fill(starts,starts+n,0);
    for(int i = 0;i<n;i++){
        set<int>val;
        for(int j = 0;j<m;j++){
            val.insert(j);
        }
        bool work = 1;
        for(int j = 0;j<m;j++){
            set<int>rem;
            for(int curr : val){
                //i+jth colour to be filled by curr+j
                int ind = ((curr+j)%m);
                //if b[ind] has c[i+j] then this is good, if now then rem
                int vind = (lower_bound(b[ind].begin(),b[ind].end(),(c[i+j]))-b[ind].begin());
                if(vind==b[ind].size()||b[ind][vind]!=c[i+j]){
                    rem.insert(curr);
                }
            }
            for(int c : rem){
                val.erase(c);
            }
            if(val.size()==0){
                work=0;
                break;
            }
        }
        starts[i]=work;
    }
    //start points discovered
    int ans = 0;
    if(starts[0]==0){
        return -1;
    }
    for(int i = 0;i<n;i++){
        if(starts[i]){
            i+=m-1;
            ans++;
            continue;
        }
        bool wor = 0;
        for(int j = 0;j<m;j++){
            if(starts[i-j]){
                i=i-j+m-1;
                ans++;
                wor=1;
                break;
            }
        }
        if(!wor){
            return -1;
        }
    }
    return ans;
}

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