oj.uz

Submission #380888

# Submission time Handle Problem Language Result Execution time Memory
380888 2021-03-23T13:46:27 Z SolarSystem Painting Walls (APIO20_paint) C++17
0 / 100
 1 ms 492 KB 
#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() + 1].find(s[j]) != t[i - (int) s.size() + 1].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].find(s[j]) == t[i].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 < (int) b[i].size(); j++) {
            t[i].insert(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;

        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 <= k) {
                return -1;
            } else {
                cout << i << endl;
                ans++;
                k = j + m - 1;
            }
        }

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

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -