235382026-01-24 12:34:29tarjanmiciWalking In The Parkcpp17Accepted 100/100377ms37932 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <climits>
#include <array>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n+1), b(n + 1), pa(n+1), pb(n + 1);
    map<ll, ll> ind;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        pa[i] = pa[i - 1] + a[i];
    }
    for (ll i = 1; i <= m; i++) {
        cin >> b[i];
        pb[i] = pb[i - 1] + b[i];
        ind[pb[i]] = i;
    }
    vector<ll>lis(n + 1);
    for (ll i = 1; i <= n; i++) {
        lis[i] = ind[pa[i]];
    }
    vector<ll> dp(n + 1, LLONG_MAX), bck(n + 1), ki(n+1);
    ll mx = 0, kii=0;
    for (ll i = 1; i <= n; i++) {
        ll x = lower_bound(dp.begin(), dp.end(), lis[i]) - dp.begin();
        if (mx < x + 1) {
            mx = x + 1;
            kii = i;
        }
        if (lis[i]) {
            dp[x] = lis[i];
            ki[x] = i;
            if(x>0)
            bck[i] = ki[x-1];
        }
    }
    vector<int> a1, a2;
    if (mx < k||pa[n]!=pb[m]) {
        cout << "-1\n";
    }
    else {
        int szml = 0;
        for (int i = bck[kii]; szml<k-1; i = bck[i]) {
            a1.push_back(i);
            a2.push_back(lis[i]);
            szml++;
        }
        reverse(a1.begin(), a1.end());
        reverse(a2.begin(), a2.end());
        for (int i = 0; i < a1.size(); i++) {
            cout << a1[i] << ' ';
        }
        cout << '\n';
        for (int i = 0; i < a2.size(); i++) {
            cout << a2[i] << ' ';
        }
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms500 KiB
2Accepted1ms316 KiB
subtask219/19
3Accepted214ms37932 KiB
4Accepted202ms37676 KiB
5Accepted203ms37168 KiB
6Accepted211ms36656 KiB
7Accepted214ms37172 KiB
8Accepted201ms36656 KiB
9Accepted216ms35952 KiB
subtask323/23
10Accepted2ms316 KiB
11Accepted2ms316 KiB
12Accepted1ms500 KiB
13Accepted1ms508 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
subtask416/16
16Accepted2ms564 KiB
17Accepted2ms576 KiB
18Accepted2ms456 KiB
19Accepted2ms564 KiB
20Accepted2ms564 KiB
21Accepted2ms564 KiB
22Accepted2ms564 KiB
subtask542/42
23Accepted377ms31532 KiB
24Accepted319ms31540 KiB
25Accepted377ms31536 KiB
26Accepted314ms31016 KiB
27Accepted296ms31540 KiB
28Accepted326ms31028 KiB
29Accepted282ms31144 KiB