Submission #502862

#	Time	Username	Problem	Language	Result	Execution time	Memory
502862		Victor	Painting Walls (APIO20_paint)	C++17	100 / 100	1341 ms	15912 KiB

paint

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    int jmp_back[100005];
    vi colors[100005];
    vector<bool> possible, added;
    possible.assign(N, 0);
    added.resize(2 * M);
    const int n = N, m = M;

    rep(i, 0, m) trav(color, B[i]) colors[color].pb(i);

    vi dp(n, 0), dp2(n, 0), vis(n, n - 1);
    per(i, 0, n) {
        int color = C[i];
        // debug(i);
        trav(person, colors[color]) {
            // cout<<"person = "<<person+1<<" dp[person] = "<<dp[person]<<" vis[person] = "<<vis[person]<<endl;
            if(vis[person]!=i) dp[person]=0;
            dp2[(person - 1 + m) % m] = dp[person] + 1;
            if (dp2[(person - 1 + m) % m] >= m) possible[i] = 1;
        }
        trav(person, colors[color]) vis[(person - 1 + m) % m]=i-1;
        // cout<<endl;
        dp.swap(dp2);
    }

    int val = -INF;
    rep(i, 0, n) {
        if (possible[i]) val = i;
        jmp_back[i] = val;
    }

    int pos = 0, ans = 0;
    while (pos < n) {
        int nxt_pos = jmp_back[pos];
        if (nxt_pos + m > pos) {
            pos = nxt_pos + m;
            ++ans;

        } else
            return -1;
    }
    return ans;
}
/*
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;
}*/

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