oj.uz

Submission #979651

# Submission time Handle Problem Language Result Execution time Memory
979651 2024-05-11T09:27:19 Z vjudge1 Painting Walls (APIO20_paint) C++17
0 / 100
 1 ms 4444 KB 
#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;
}

Compilation message

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:90:23: warning: logical not is only applied to the left hand side of comparison [-Wlogical-not-parentheses]
   90 |         if (!to[i][0] == i) {
      |                       ^~
paint.cpp:90:13: note: add parentheses around left hand side expression to silence this warning
   90 |         if (!to[i][0] == i) {
      |             ^~~~~~~~~
      |             (        )

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -