oj.uz

답안 #444668

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444668 2021-07-14T16:20:23 Z prvocislo Matching (CEOI11_mat) C++17
100 / 100
 441 ms 47964 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1e6 + 5;
int s[maxn]; // povodne pole
int p[maxn]; // p[i] = relativna vyska i-teho schodiku
int nx[maxn], pv[maxn]; // polia pre linked list. Indexujeme do nich poradim. Cize na zaciatku su vsetky prvky zlinkovane v poradi 0, ..., n-1.
int dist_pv[maxn], dist_nx[maxn]; // o kolko dozadu sa nachadza prvok ktory je tesne mensi/vacsi ako ja?
int h[maxn]; // vysky budov
int f[maxn]; // failure funkcia pre KMP
bool ok(int i, int j, int *text) // mozeme posunut index j v patterne ak dalsi znak je text[i]?
{
    if ((!dist_pv[j+1] || text[i-dist_pv[j+1]] < text[i]) && (!dist_nx[j+1] || text[i-dist_nx[j+1]] > text[i])) return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
        p[--s[i]] = i;
        nx[i] = i+1, pv[i] = i-1;
    }
    for (int i = n-1; i >= 0; i--)
    {
        if (pv[p[i]] != -1) // najblizsi mensi prvok v mojom prefixe
        {
            dist_pv[i] = i - s[pv[p[i]]]; // p[i] je hodnota mojho prvku, pv[p[i]] je najblizsi mensi
            nx[pv[p[i]]] = nx[p[i]];
        }
        if (nx[p[i]] != n) // najblizsi vacsi prvok v mojom prefixe
        {
            dist_nx[i] = i - s[nx[p[i]]]; // p[i] je hodnota mojho prvku, nx[p[i]] je najblizsi vacsi
            pv[nx[p[i]]] = pv[p[i]];
        }
    }
    f[0] = -1;
    for (int i = 1, j = f[0]; i < n; i++)
    {
        while (j != -1 && !ok(i, j, p)) j = f[j];
        if (ok(i, j, p)) j++;
        f[i] = j;
    }
    vector<int> ans;
    for (int i = 0, j = -1; i < m; i++)
    {
        cin >> h[i];
        while (j != -1 && !ok(i, j, h)) j = f[j];
        if (ok(i, j, h)) j++;
        if (j == n-1)
        {
            ans.push_back(i-(n-1));
            j = f[j];
        }
    }
    cout << ans.size() << "\n";
    for (int i : ans) cout << i+1 << " ";
    cout << "\n";
    return 0;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 3 ms 716 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 716 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 3588 KB Output is correct
2 Correct 23 ms 2548 KB Output is correct
3 Correct 37 ms 4676 KB Output is correct
4 Correct 37 ms 4704 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 4464 KB Output is correct
2 Correct 33 ms 3220 KB Output is correct
3 Correct 35 ms 3936 KB Output is correct
4 Correct 53 ms 4532 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 4552 KB Output is correct
2 Correct 30 ms 3880 KB Output is correct
3 Correct 30 ms 3780 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 21332 KB Output is correct
2 Correct 441 ms 47964 KB Output is correct
3 Correct 113 ms 11840 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 22756 KB Output is correct
2 Correct 130 ms 10948 KB Output is correct
3 Correct 383 ms 43460 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 14532 KB Output is correct
2 Correct 212 ms 21960 KB Output is correct
3 Correct 146 ms 16092 KB Output is correct
4 Correct 256 ms 45964 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 16244 KB Output is correct
2 Correct 153 ms 16368 KB Output is correct
3 Correct 73 ms 9156 KB Output is correct
4 Correct 254 ms 43764 KB Output is correct