Submission #1032192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032192		Tonyl	Painting Walls (APIO20_paint)	C++17	63 / 100	1580 ms	14800 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
using ll = long long;
#define REP(i,n) for (int i = 0; i < n; i++)
#define trav(a,x) for (auto &a : x)
#define all(x) (x).begin(), (x).end()
#define D(x) cerr << #x << ": " << x << endl;

const int MAX_K = 100001;
const int MAX_M = 50001;
const int MAX_N = MAX_K;
int n,m,k;

vi col_to_contr[MAX_K];
vi cols;
int counts[MAX_M];
set<int> work;
bool able[MAX_N];

vi get_mods(int i) {
  vi mods;
  trav(contr, col_to_contr[cols[i]]) {
    mods.push_back((contr-(i%m)+m)%m);
  }
  return mods;
}

void add_tile(int i) {
  vi mods = get_mods(i);
  trav (mod, mods) {
    counts[mod]++;
    if (counts[mod] == m) work.insert(mod);
  }
}

void remove_tile(int i) {
  vi mods = get_mods(i);
  trav (mod, mods) {
    if (counts[mod] == m) work.erase(mod);
    counts[mod]--;
  }
}

int dp_ans() {
  vi dp(n, 1e9);
  deque<pi> q;
  if (able[0]) dp[0] = 1;
  q.push_back({dp[0], 0});
  for (int i = 1; i <= n-m; i++) {
    // remove old
    while (q.size() && q.front().second < i-m) q.pop_front();

    if (able[i]) {
      // get min
      int minn = q.front().first;
      dp[i] = minn+1;
    }
    
    // push new
    while (q.size() && q.back().first >= dp[i]) q.pop_back();
    q.push_back({dp[i], i});
  }
  if (dp[n-m] > n) return -1;
  return dp[n-m];
}

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
  n = N; m = M; k = K;
  cols = C;
  REP(i,m) {
    REP(j,A[i]) {
      col_to_contr[B[i][j]].push_back(i);
    }
  }

  REP(i,m) add_tile(i);
  if (work.size()) able[0] = 1;

  for (int i = 1; i <= n-m; i++) {
    // move
    remove_tile(i-1);
    add_tile(i+m-1);
    if (work.size()) able[i] = 1;
  }

  /*D(n);
  D(m);
  REP(i, n-m) {
    if (able[i]) cerr << "1";
    else cerr << "0";
  }
  cerr << endl;*/

  return dp_ans();
}

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