235352026-01-24 12:13:48KateTaylorWalking In The Parkcpp17Accepted 100/100324ms21156 KiB
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	vector<ll> a(n), b(m);
	vector<pair<ll, int>> v;
	map<ll, int> pos;
	cin >> a[0];
	for (int i = 1; i < n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	cin >> b[0];
	pos[b[0]] = 0;
	for (int i = 1; i < m; i++) {
		cin >> b[i];
		b[i] += b[i - 1];
		pos[b[i]] = i;
	}
	if (a.back() != b.back()) {
		cout << -1;
		return 0;
	}
	for (int i = 0; i < n; i++) {
		if (!pos.count(a[i])) continue;
		v.push_back({ pos[a[i]], i });
	}
	vector<pair<ll, int>> dp = { {(ll)1e18, 1e9} };
	vector<int> par(n, -1);
	for (auto p : v) {
		int i = p.second, x = p.first;
		int pp = lower_bound(dp.begin(), dp.end(), make_pair((ll)x, 0)) - dp.begin();
		if (pp == dp.size() - 1) {
			dp[pp] = p;
			dp.push_back({ (ll)1e18, 1e9 });
		}
		else dp[pp] = p;
		if (pp) par[i] = dp[pp - 1].second;
	}
	vector<int> ans;
	int curr = n - 1;
	while (ans.size() < k && curr != -1) {
		ans.push_back(curr);
		curr = par[curr];
	}
	if (ans.size() < k) {
		cout << -1;
		return 0;
	}
	reverse(ans.begin(), ans.end());
	ans.pop_back();
	for (int x : ans) cout << ++x << " ";
	cout << "\n";
	for (int x : ans) cout << pos[a[x]] + 1 << " ";
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
subtask219/19
3Accepted172ms16880 KiB
4Accepted165ms17148 KiB
5Accepted174ms17768 KiB
6Accepted166ms17764 KiB
7Accepted175ms17900 KiB
8Accepted122ms15924 KiB
9Accepted202ms19360 KiB
subtask323/23
10Accepted1ms512 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
subtask416/16
16Accepted2ms316 KiB
17Accepted2ms352 KiB
18Accepted2ms316 KiB
19Accepted2ms316 KiB
20Accepted2ms316 KiB
21Accepted1ms316 KiB
22Accepted2ms316 KiB
subtask542/42
23Accepted291ms18276 KiB
24Accepted298ms18524 KiB
25Accepted300ms19444 KiB
26Accepted314ms19292 KiB
27Accepted324ms19556 KiB
28Accepted136ms15916 KiB
29Accepted275ms21156 KiB