Submission #926569

#	Time	Username	Problem	Language	Result	Execution time	Memory
926569		green_gold_dog	Painting Walls (APIO20_paint)	C++17	28 / 100	1525 ms	21588 KiB

paint

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

typedef int ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
        if (b > a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_min(T& a, T b) {
        if (b < a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
T square(T a) {
        return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
        ll operator() (pair<ll, ll> p) const {
                return ((__int128)p.first * MOD + p.second) % INF64;
        }
};

ll add(ll x, ll m) {
        x++;
        if (x == m) {
                x = 0;
        }
        return x;
}

ll sub(ll x, ll m) {
        x--;
        if (x == -1) {
                x = m - 1;
        }
        return x;
}

ll minimumInstructions(ll n, ll m, ll k, vector<ll> c, vector<ll> a, vector<vector<ll>> b) {
        vector<unordered_set<ll>> all(k);
        for (ll i = 0; i < m; i++) {
                for (auto j : b[i]) {
                        all[j].insert(i);
                }
        }
        vector<ll> col(m);
        for (ll i = 0; i < n; i++) {
                for (auto j : all[c[i]]) {
                        col[j]++;
                }
        }
        ll sum = col[0] + col.back(), now = 0, lst = m - 1;
        for (ll i = 1; i < m; i++) {
                if (assign_min(sum, col[i] + col[i - 1])) {
                        now = i;
                        lst = i - 1;
                }
        }
        vector<ll> cnow(n, 0), clst(n, 0);
        for (ll i = 0; i < n; i++) {
                ll nn = i, nx = now;
                while (nn < n) {
                        if (all[c[nn]].find(nx) == all[c[nn]].end()) {
                                break;
                        }
                        cnow[i]++;
                        nx = add(nx, m);
                        nn++;
                }
                nn = i;
                nx = lst;
                while (nn >= 0) {
                        if (all[c[nn]].find(nx) == all[c[nn]].end()) {
                                break;
                        }
                        clst[i]++;
                        nx = sub(nx, m);
                        nn--;
                }
        }
        vector<bool> cand(n, false);
        deque<ll> ta, td;
        for (ll i = 0; i < n; i++) {
                ll sum = cnow[i];
                ll st = i;
                if (i != 0) {
                        sum += clst[i - 1];
                        st -= clst[i - 1];
                }
                if (sum >= m) {
                        ta.push_back(st);
                        td.push_back(st + sum - m);
                }
        }
        ll ns = 0;
        sort(ta.begin(), ta.end());
        sort(td.begin(), td.end());
        for (ll i = 0; i < n; i++) {
                while (!ta.empty() && ta.front() == i) {
                        ns++;
                        ta.pop_front();
                }
                cand[i] = ns > 0;
                while (!td.empty() && td.front() == i) {
                        ns--;
                        td.pop_front();
                }
        }
        lst = 0;
        ll can = 0;
        ll ans = 0;
        while (can < n) {
                ll ncan = can;
                for (ll j = lst; j <= can; j++) {
                        if (cand[j]) {
                                assign_max(ncan, j + m);
                        }
                }
                lst = can + 1;
                if (ncan == can) {
                        return -1;
                }
                ans++;
                can = ncan;
        }
        return ans;
}

#ifdef LOCAL
int main() {
  int N, M, K;
  assert(3 == scanf("%d %d %d", &N, &M, &K));

  std::vector<int> C(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &C[i]));
  }

  std::vector<int> A(M);
  std::vector<std::vector<int>> B(M);
  for (int i = 0; i < M; ++i) {
    assert(1 == scanf("%d", &A[i]));
    B[i].resize(A[i]);
    for (int j = 0; j < A[i]; ++j) {
      assert(1 == scanf("%d", &B[i][j]));
    }
  }

  int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
  printf("%d\n", minimum_instructions);

  return 0;
}
#endif

Compilation message (stderr)

paint.cpp:13:22: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '9000000000000000000' to '-494665728' [-Woverflow]
   13 | constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
      |                      ^~~~~~~~~~~~~~~~~~~~~~~~~

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