Submission #698056

#	Time	Username	Problem	Language	Result	Execution time	Memory
698056		fatemetmhr	Painting Walls (APIO20_paint)	C++17	100 / 100	374 ms	14668 KiB

paint

// ~~ Be name khoda ~~
 
#include "paint.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
 
const int maxn5 = 1e5 + 10;
const int maxn  = 2e4 + 10;
const int maxm  = 2e3 + 10;
 
int have[2][maxn5];
vector <int> out, av[maxn5];
 
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B){
    int n = N, m = M;
    for(int i = 0; i < m; i++) for(auto u : B[i])
        av[u].pb(i);
    if(m == 1){
        bool re = true;
        for(int i = 0; i < n; i++)
            re &= (av[C[i]].size() > 0);
        return (re ? n : -1);
    }
    for(auto id : av[C[0]])
        have[0][id] = 1;
    out.pb(-1);
    for(int i = 1; i < n; i++){
        int len = 0;
        for(auto id : av[C[i]])
            len = max(len, have[i&1][id] = have[(i&1)^1][id == 0 ? m - 1 : id - 1] + 1);
        for(auto id : av[C[i - 1]])
            have[(i&1)^1][id] = 0;
        if(len >= m){
            while(out.size() > 1 && i - out[out.size() - 2] <= m)
                out.pop_back();
            if(i - out.back() > m)
                return -1;
            out.pb(i);
        }
    }
    if(out.back() != n - 1)
        return -1;
    return out.size() - 1;
}
 
// hen?

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