Submission #892093

#	Time	Username	Problem	Language	Result	Execution time	Memory
892093		omeganot	Painting Walls (APIO20_paint)	C++11	63 / 100	598 ms	524288 KiB

paint

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int MOD = 1E9 + 7;
const int INF = 1E9; const ll INFLL = 1E18;

const int MAX = 6E7;

int val[MAX];
int len[MAX];
int group[MAX];

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    if(M > 1) {
        vector<int> bv(N + 1);
        vector<int> cnt(K);
        int unique = 0;
        for(int i = 0; i < M; i++) {
            if(!cnt[C[i]]) {
                unique++;
            }
            cnt[C[i]]++;
        }
        if(unique * 632 < M) {
            return -1;
        } else {
            bv[0]++;
            bv[M]--;
        }
        for(int i = 0; i + M < N; i++) {
            if(cnt[C[i]] == 1) {
                unique--;
            }
            cnt[C[i]]--;
            if(!cnt[C[i + M]]) {
                unique++;
            }
            if(unique * 632 >= M) {
                bv[i + 1]++;
                bv[i + M + 1]--;
            }
        }
        for(int i = 1; i < N; i++) {
            bv[i] += bv[i - 1];
            if(!bv[i]) {
                return -1;
            }
        }
    }
    vector<basic_string<int>> kc(K);
    for(int i = 0; i < M; i++) {
        for(int j : B[i]) {
            kc[j].push_back(i);
        }
    }
    vector<basic_string<int>> a(N);
    int curr = 0;
    vector<basic_string<int>> pos(M);
    for(int i = 0; i < N; i++) {
        a[i] = kc[C[i]];
        for(int j = 0; j < a[i].size(); j++) {
            val[curr] = a[i][j];
            pos[a[i][j]].push_back(curr);
            a[i][j] = curr;
            group[curr] = i;
            curr++;
        }
    }
    vector<int> ind(M);
    for(int i = 0; i + 1 < N; i++) {
        for(int j : a[i]) {
            ind[val[j]]++;
        }
        for(int j = 0; j < a[i].size(); j++) {
            int v = val[a[i][j]];
            if(ind[(v + 1) % M] < pos[(v + 1) % M].size() && group[pos[(v + 1) % M][ind[(v + 1) % M]]] == i + 1) {
                len[pos[(v + 1) % M][ind[(v + 1) % M]]] = len[a[i][j]] + 1;
            }
        } 
    }
    int currR = -1;
    int maxR = -1;
    bool ok = true;
    int ans = 0;
    for(int i = 0; i + M - 1 < N; i++) {
        if(currR + 1 < i) {
            ok = false;
            break;
        }
        for(int j : a[i + M - 1]) {
            if(len[j] >= M - 1) {
                maxR = max(maxR, i + M - 1);
            }
        }
        if(currR < i) {
            ans++;
            currR = maxR;
        }
    }
    if(maxR != N - 1) {
        ok = false;
    }
    if(currR + 1 < N) {
        ans++;
    }
    return (ok ? ans : -1);  
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 0; j < a[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~
paint.cpp:76:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int j = 0; j < a[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~
paint.cpp:78:33: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::__cxx11::basic_string<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             if(ind[(v + 1) % M] < pos[(v + 1) % M].size() && group[pos[(v + 1) % M][ind[(v + 1) % M]]] == i + 1) {

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