Submission #979652

#	Time	Username	Problem	Language	Result	Execution time	Memory
979652		vjudge1	Painting Walls (APIO20_paint)	C++17	28 / 100	952 ms	324180 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;
using ll = long long;

const int N = 20200;
const int M = 2020;

int n, m;

int g[N][M];
int f[N][M];

void precalc() {
    for (int j = 0; j < m; j++) {
        int x = n - 1, y = j;
        while (g[x][y] && f[n - 1][j] < m) {
            f[n - 1][j]++;
            x = (x + 1) % n;
            y = (y + 1) % m;
        }
    }

    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < m; j++) {
            if (g[i][j]) f[i][j] = 1 + f[i + 1][(j + 1) % m];
            else f[i][j] = 0;
        }
    }
}

int to[N][18];
int dt[N][18];

int minimumInstructions(
    int N, int M, int K, vector<int> C,
    vector<int> A, vector<vector<int>> B) {
    n = N,
    m = M;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x = lower_bound(B[j].begin(), B[j].end(), C[i]) - B[j].begin();
            g[i][j] = (x != A[j] && B[j][x] == C[i]);

        }
    }

    precalc();
    bool able[n] = {};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) 
            able[i] |= (f[i][j] >= m);
        // cout << able[i] << ' ';
    }
    // cout << '\n';
    {
        int st = 0;
        while (st < n && !able[st]) st++;
        if (st == n) return -1;
        if (m == n)
            return 1;
        
        int nxt = 0, w = 0;
        for (int i = 0; i < n; i++) {
            if (able[(i + st) % n]) {
                nxt = (i + st + m) % n;
                w = 0;
            } 
            if (w >= m) nxt = (st + i) % n;
            to[(i + st) % n][0] = nxt;
            dt[(i + st) % n][0] = (nxt - st - i + 2 * n) % n;
            w++;
        }
        // for (int i = 0; i < n; i++)
        //     cout << to[(i + st) % n][0] << ' ';
        // cout << '\n';
        // for (int i = 0; i < n; i++)
        //     cout << dt[(i + st) % n][0] << ' ';
        // cout << '\n';
    }
    for (int k = 1; k < 18; k++) {
        for (int i = 0; i < n; i++) {
            to[i][k] = to[to[i][k - 1]][k - 1];
            dt[i][k] = dt[i][k - 1] + dt[to[i][k - 1]][k - 1];
        }
    }
    for (int i = 0; i < n; i++) {
        if (to[i][0] == i) {
            return -1;
        }
    }
    int res = n + 1;
    for (int i = 0; i < n; i++) {
        int x = i;
        int ans = 0;
        int dist = 0;
        for (int k = 17; k >= 0; k--) {
            if (dist + dt[x][k] < n) {
                ans += (1 << k);
                dist += dt[x][k];
                x = to[x][k];
            }
        }
        res = min(res, ans + 1);
    }
    if (res == n + 1) return -1;
    return res;
}

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