Submission #977284

#	Time	Username	Problem	Language	Result	Execution time	Memory
977284		kwongweng	Painting Walls (APIO20_paint)	C++17	100 / 100	462 ms	13652 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef vector<vector<ll>> vll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second

int minimumInstructions(int N, int M, int K, vi C, vi A, vector<vi> B) {
  vi col[K]; // col[i] contains indices of contractors who like colour i
  FOR(i,0,M){
    FOR(j,0,A[i]){
      col[B[i][j]].pb(i);
    }
  }
  vi pos(N+1); //pos[i]=1 iff it's possible to colour positions i,i+1,...,i+M-1
  vii len(M); 
  ROF(i,N-1,0){
    //makes len[u] = max length of segment that can be covered if contractor u colours i, u+1 colours i+1 and so on
    int sz = col[C[i]].size();
    vii val(sz); FOR(j,0,sz){
      int u = (col[C[i]][j]+1)%M;
      val[j] = len[u];
    }
    FOR(j,0,sz){
      //iterating contractors who like colour C[i]
      int u = col[C[i]][j];
      if (val[j].se != i+1){
        len[u] = {1,i}; //nxt cannot colour i+1
      }else{
        len[u] = {min(val[j].fi+1,M),i};
      }
      if (len[u].fi == M) pos[i]=1; //no overflow since this can only activate when i<N-M
    }
  }
  //FOR(i,0,N-M+1) cout<<pos[i]<<" "; cout<<"\n";
  if (!pos[0] || !pos[N-M]) return -1;
  int cur = 0, nxt = -1, cnt=1;
  FOR(i,1,N+1){
    if (i-cur>M){
      if (nxt==-1) return -1;
      cur = nxt; cnt++; nxt=-1;
    }
    if (pos[i]){
      nxt=i;
    }
  }
  return cnt;
}

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