Submission #380913

#	Time	Username	Problem	Language	Result	Execution time	Memory
380913		SolarSystem	Painting Walls (APIO20_paint)	C++17	0 / 100	1580 ms	10732 KiB

paint

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <stdio.h>
#include <numeric>
#include <iomanip>
#include <unordered_set>

using namespace std;

vector<unordered_set<int>> t;

bool check(vector<int> s) {
    s.push_back(-1);
    vector<int> pi(s.size() + t.size());
    pi[0] = 0;

    for (int i = 1; i < (int) pi.size(); i++) {
        int j = pi[i - 1];

        while (j > 0) {
            if (i < (int) s.size() && s[j] != s[i]) {
                j = pi[j - 1];
            } else if (i >= (int) s.size() && t[i - (int) s.size()].find(s[j]) == t[i - (int) s.size()].end()) {
                j = pi[j - 1];
            } else {
                break;
            }
        }

        if (i < (int) s.size() && s[j] == s[i]) {
            j++;
        } else if (i >= (int) s.size() && t[i - (int) s.size()].find(s[j]) != t[i - (int) s.size()].end()) {
            j++;
        }

        pi[i] = j;
    }

    for (int u: pi) {
        if (u == (int) s.size() - 1) {
            return true;
        }
    }

    return false;
}

int minimumInstructions(int n, int m, int k1, vector<int> c, vector<int> a, vector<vector<int>> b) {
    t.resize(m);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < a[i]; j++) {
            t[i].insert(b[i][j]);
        }
    }

    for (int i = 0; i < m; i++) {
        t.push_back(t[i]);
    }

    int ans = 0;

    int j = -1, k = -1;

    for (int i = 0; ; i++) {
        vector<int> e;

        if (i + m - 1 < n) {
            for (int j = i; j <= i + m - 1; j++) {
                e.push_back(c[j]);
            }

            if (check(e)) {
                j = i;
            }
        }

        if (i > k) {
            if (j + m - 1 < i) {
                return -1;
            } else {
                ans++;
                k = j + m - 1;
            }
        }

        if (k == n - 1) {
            return ans;
        }
    }
}

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