Submission #1193584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193584		vyaduct	Painting Walls (APIO20_paint)	C++20	12 / 100	45 ms	17224 KiB

paint

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define vt vector
#define F first
#define S second
#define pii pair<ll,ll>
#define pb push_back

int subtask1(int n, int m, vt<int> &C, vt<ll> &pos){
   for (int i=1;i<n;i++){
    int a = pos[C[i-1]];
    int b = pos[C[i]];
    if (a == m-1) {
      if (b != 0) return -1;
    } else {
      if (b != a+1) return -1;
    }
  }
  return (n+m-1)/m;
}

bool valid(int i, int j, int m){
  return (i+1)%m == j;
}

// returns if there is i,j in L,R such that valid(i,j) = true
// aka, can we go from C[i] to C[j]
// O(|L| log (|R|))
bool ok(set<ll> &L, set<ll> &R, ll m){
  for (auto x: L){
    int y = (x+1)%m;
    if (R.count(y)) return true;
  }
  return false;
}

vt<pii> runlen(vt<bool> a){
  vt<pii> res;
  ll cnt=1, last = a[0];
  for (int i=1;i<a.size();i++){
    if (a[i] == last) cnt++;
    else {
      res.pb({last, cnt});
      cnt = 1;
      last = a[i];
    }
  }
  res.pb({last, cnt});
  return res;
}

int minimumInstructions(int n, int m, int k, vt<int> C, vt<int> A, vt<vt<int>> B){
  bool s1=true;
  vt<ll> fpos(k, -1);
  vt<set<ll>> pos(k);
  for (int i=0;i<m;i++){
    for (auto x: B[i]){
      if (fpos[x] != -1) s1 = false;
      fpos[x] = i;
      pos[x].insert(i);
    }
  }
  if (s1) return subtask1(n, m, C, fpos);

  // window movement
  vt<bool> V;
  for (ll i=0;i+1<n;i++){
    auto sa = pos[C[i]];
    auto sb = pos[C[i+1]];
    bool flag = ok(sa, sb, m);
    V.pb(flag);
  }

  vt<pii> r = runlen(V);

  ll cnt=1e9;
  for (int j=0;j<sz(r);j++){
    ll cur=0;
    int mm = sz(r);
    int i = j % mm;
    while(mm--){
      int x = r[i].F, c = r[i].S;
      int cc = c+1;
      if (x == 0 && cc>= m) {cur = -1; break;}
      if (x == 1){
        int add = (cc+m-1)/m;;
        if (add == 0) cur = -1;
        else cur += add;
      }
      i = (i+1) % sz(r);
    }
    if (cur != -1) cnt = min(cnt, cur);
  }
  return (cnt == 1e9 ? -1 : cnt);
}

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