Submission #979674

#	Time	Username	Problem	Language	Result	Execution time	Memory
979674		vjudge1	Painting Walls (APIO20_paint)	C++17	28 / 100	984 ms	327008 KiB

paint

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

using namespace std;
using ll = long long;

const int N1 = 20200;
const int M1 = 2020;

int n, m;

int g[N1][M1];
int f[N1][M1];

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;
        }
    }
}

const int N = 100100;

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;

    bool able[n] = {};

    if (n < N1 && m < M1) {
        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();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) 
                able[i] |= (f[i][j] >= m);
        }
    } else {
        bool used[K + 1] = {};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < A[i]; j++) {
                used[B[i][j]] = true;
            }
        }
        int cnt = 0;
        map<int, int> mp;
        for (int i = 0; i < m; i++) {
            mp[C[i]]++;
            cnt += used[i];
        }

        for (int i = 0; i < n; i++) {
            able[i] = ((int)mp.size() == m && cnt == m);
            cnt -= used[C[i]];
            cnt += used[C[(i + m) % n]]; 
            mp[C[i]]--;
            mp[C[(i + m) % n]]++;
            if (!mp[C[i]]) mp.erase(C[i]);
        }
    }
    
    {
        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 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];
        }
    }
    
    int res = 1e9;
    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];
            }
        }
        if (dist + dt[x][0] >= n)
            res = min(res, ans + 1);
    }
    if (res == 1e9) return -1;
    return res;
}

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