oj.uz

Submission #966520

# Submission time Handle Problem Language Result Execution time Memory
966520 2024-04-20T02:54:22 Z gaga999 Painting Walls (APIO20_paint) C++17
0 / 100
 5 ms 8284 KB 
#include <cstdio>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100005;
vector<int> d[maxn];
int n, m, k, vis[2][maxn], dp[2][maxn], ok[maxn];
struct node
{
    int l, r;
} s[maxn];
bool cmp(node a, node b)
{
    return a.l < b.l;
}
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B)
{
    n = N;
    m = M;
    k = K;
    for (int i = 1; i <= n; i++)
        C[i - 1]++;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j < A[i - 1]; j++)
            B[i - 1][j]++;
    }
    for (int i = 1; i < maxn; i++)
        d[i].push_back(0);
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j < A[i - 1]; j++)
            d[B[i - 1][j]][0]++, d[B[i - 1][j]].push_back(i);
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = 1; j <= d[C[i - 1]][0]; j++)
        {
            if (vis[(i + 1) & 1][d[C[i - 1]][j] % m + 1] == i + 1)
                dp[i & 1][d[C[i - 1]][j]] = dp[(i + 1) & 1][d[C[i - 1]][j] % m + 1] + 1;
            else
                dp[i & 1][d[C[i - 1]][j]] = 1;
            vis[i & 1][d[C[i - 1]][j]] = i;
            if (dp[i & 1][d[C[i - 1]][j]] >= m)
                ok[i] = 1;
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n - m + 1; i++)
    {
        if (ok[i])
        {
            cnt++;
            s[cnt].l = i;
            s[cnt].r = i + m - 1;
        }
    }
    if (!ok[1] || !ok[n - m + 1])
        return -1;
    else if (n == m)
        return 1;
    int l = 1, r = m + 1, ans = 1;
    for (int i = 1; i <= n; i++)
    {
        while (i < r)
            if (ok[++i])
                l = i;
        if (l == r - m)
            return -1;
        ans++, r = l + m;
        if (r == n + 1)
            return ans;
    }
    return -1;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6236 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 4 ms 6236 KB Output is correct
4 Correct 5 ms 8280 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 5 ms 6236 KB Output is correct
7 Incorrect 5 ms 8284 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6236 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 4 ms 6236 KB Output is correct
4 Correct 5 ms 8280 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 5 ms 6236 KB Output is correct
7 Incorrect 5 ms 8284 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6236 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 4 ms 6236 KB Output is correct
4 Correct 5 ms 8280 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 5 ms 6236 KB Output is correct
7 Incorrect 5 ms 8284 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6236 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 4 ms 6236 KB Output is correct
4 Correct 5 ms 8280 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 5 ms 6236 KB Output is correct
7 Incorrect 5 ms 8284 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6236 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 4 ms 6236 KB Output is correct
4 Correct 5 ms 8280 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 5 ms 6236 KB Output is correct
7 Incorrect 5 ms 8284 KB Output isn't correct
8 Halted 0 ms 0 KB -