oj.uz

Submission #697509

# Submission time Handle Problem Language Result Execution time Memory
697509 2023-02-10T07:20:13 Z sharaelong Painting Walls (APIO20_paint) C++17
0 / 100
 0 ms 212 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 1;

bool processed[MAX_N][633];

int minimumInstructions(int n, int m, int k, vector<int> C, vector<int> A, vector<vector<int>> B) {
    vector<vector<int>> likes(k);
    for (int i=0; i<m; ++i) {
        for (int j=0; j<A[i]; ++j) {
            likes[B[i][j]].push_back(i);
        }
    }
    for (int i=0; i<k; ++i) likes[i].push_back(m+100);
    // for (int i=0; i<k; ++i) {
    //     for (int x: likes[i]) cout << x << ' ';
    //     cout << endl;
    // }
    
    vector<vector<int>> nxt(n);
    for (int i=0; i<n; ++i) {
        nxt[i].resize(likes[C[i]].size(), -1);
    }

    for (int i=0; i+1<n; ++i) {
        int pnt = 0;
        const vector<int>& cands = likes[C[i+1]];
        for (int j=0; j<likes[C[i]].size(); ++j) {
            int x = likes[C[i]][j];
            if (x+1 < m) {
                // while (pnt < cands.size() && cands[pnt] <= x) pnt++;
                // if (pnt < cands.size() && cands[pnt] == x+1) nxt[i][j] = pnt;
                while (cands[pnt] <= x) pnt++;
                if (cands[pnt] == x+1) nxt[i][j] = pnt;
            } else {
                if (!cands.empty() && cands[0] == 0) nxt[i][j] = 0;
            }
        }
    }
    // for (int i=0; i<n; ++i) {
    //     for (int x: nxt[i]) cout << x << ' ';
    //     cout << endl;
    // }

    vector<int> okay(n+1, 0);
    for (int i=0; i<n; ++i) {
        for (int j=0; j<likes[C[i]].size(); ++j) {
            if (!processed[i][j]) {
                // processed[i][j] = true;
                int ii = i, jj = j;
                // while (ii < n && nxt[ii][jj] != -1) {
                while (nxt[ii][jj] != -1) {
                    jj = nxt[ii][jj];
                    ii++;
                    processed[ii][jj] = true;
                }

                // if (ii == n) ii--;
                if (ii-i+1 >= m) {
                    okay[i]++;
                    okay[ii-m+2]--;
                }
            }
        }
    }
    for (int i=1; i<okay.size(); ++i) okay[i] += okay[i-1];
    // for (int i=0; i<n; ++i) cout << okay[i] << ' ';
    // cout << endl;

    vector<int> valid_pos;
    for (int i=0; i<n; ++i) {
        if (okay[i] > 0) valid_pos.push_back(i);
    }
    if (valid_pos.empty() || valid_pos[0] > 0) return -1;

    int ans = 1;
    int curr = 0;
    while (curr + m < n) {
        auto it = upper_bound(valid_pos.begin(), valid_pos.end(), curr+m);
        if (*prev(it) == curr) return -1;
        curr = *prev(it);
        ans++;
    }
    return ans;
}

Compilation message

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:34:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int j=0; j<likes[C[i]].size(); ++j) {
      |                       ~^~~~~~~~~~~~~~~~~~~
paint.cpp:53:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int j=0; j<likes[C[i]].size(); ++j) {
      |                       ~^~~~~~~~~~~~~~~~~~~
paint.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i=1; i<okay.size(); ++i) okay[i] += okay[i-1];
      |                   ~^~~~~~~~~~~~

Subtask #1
0 / 12.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 37.0

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