Submission #576786

#	Time	Username	Problem	Language	Result	Execution time	Memory
576786		radal	Painting Walls (APIO20_paint)	C++17	100 / 100	776 ms	408928 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#pragma GCC target("sse,sse2,sse4,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e5+20,mod = 998244353,inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
//    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
vector<int> f[N],a,c;
vector<vector<int> > b;
int n,m,k,dp[N];
vector<int> lst[N];
int minimumInstructions(int nn,int mm,int kk,vector<int> C,vector<int> A,vector<vector<int>> B){
    n = nn;
    m = mm;
    k = kk;
    c = C;
    a = A;
    b = B;
    rep(i,0,m){
        for (int x : b[i])
            f[x].pb(i);
    }
    rep(i,0,n)
        if (f[c[i]].empty()) return -1;
    for(int x : f[c[n-1]]){
        lst[n-1].pb(n-1);
    }
    dp[n-1] = n-1;
    repr(i,n-2,0){
        dp[i] = i;
        int po = 0;
        for (int x : f[c[i]]){
            int y = x+1;
            if (y == m) y = 0;
            int ind;
            if (y == 0){
                if (f[c[i+1]][0] != 0) lst[i].pb(i);
                else{
                    int cal = lst[i+1][0];
                    if (cal-i+1 > m) cal--;
                    lst[i].pb(cal);
                    dp[i] = max(dp[i],cal);
                    continue;
                }
            }
            int sz = f[c[i+1]].size();
            while (po < sz && f[c[i+1]][po] < y) po++;
            if (po == sz || f[c[i+1]][po] != y){
                lst[i].pb(i);
                continue;
            }
            ind = po;
            int cal = lst[i+1][ind];
            if (cal-i+1 > m) cal--;
            lst[i].pb(cal);
            dp[i] = max(dp[i],cal);
        }
    }
    int ans = 0;
    int cur = 0,rel = -1;
    while (cur < n){
        bool f = 0;
        repr(i,cur,rel+1){
            if(dp[i]-i+1 == m){
                cur = i+m;
                rel = i;
                f = 1; 
                break;
            }
        }
        if (!f) return -1;
        ans++;
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:51:13: warning: unused variable 'x' [-Wunused-variable]
   51 |     for(int x : f[c[n-1]]){
      |             ^

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