235402026-01-24 12:40:42BalimeWalking In The Parkcpp17Hibás válasz 0/100455ms22680 KiB
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ll n,m,k; cin>>n>>m>>k;

	map<ll,ll> ma;

	vector<ll> a(n+1), b(m+1), a2(n+1);
	ll par[200001];
	for(ll i=1; i<=n; i++)
	{
		cin>>a[i];
		a[i]+=a[i-1];
	}
	for(ll i=1; i<=m; i++)
	{
		cin>>b[i];
		b[i]+=b[i-1];
		ma.insert({b[i], i});
	}
	for(ll i=0; i<=n; i++)
	{
		if(ma.find(a[i])!=ma.end())a2[i]=ma[a[i]];
		else a2[i]=INT_MAX;
	}
	vector<ll> lis;
	vector<ll> top;
	for(ll i=0; i<=n; i++)
	{
		auto it =upper_bound(lis.begin(), lis.end(), a2[i]);
		if(it==lis.end())
		{
			lis.push_back(a2[i]);
			top.push_back(i);
			if(lis.size()>1)
			{
				par[i]=top[lis.size()-2];
			}
			else {
				par[i]=0;
			}
		}
		else 
		{
			*it=a2[i];
			top[it-lis.begin()]=i;
			if(it-lis.begin()-1>=0)par[i]=top[it-lis.begin()-1];
			else par[i]=0;
		}
	}
	/*for(ll i=0; i<=n+1; i++)
	{
		cout<<par[i]<<" ";
	}cout<<endl;*/

	if(lis.size()<k){
		cout<<-1<<endl; return 0;
	}

	ll h=par[n];

	if(a[n]!=b[m]){
		cout<<-1<<endl; return 0;
	}
	stack<ll> st;
	for(ll i=1; i<k; i++)
	{
		st.push(h);
		h=par[h];
	}
	if(st.size()<k-1)
	{
		cout<<-1<<endl;
		return 0;
	}	while(!st.empty())
	{
		cout<<st.top()<<" ";st.pop();
	}
	cout<<endl;
	h=par[n];
	for(ll i=1; i<k; i++)
	{
		st.push(a2[h]);
		h=par[h];
	}
	while(!st.empty())
	{
		cout<<st.top()<<" ";st.pop();
	}

}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Hibás válasz1ms508 KiB
subtask20/19
3Elfogadva284ms22376 KiB
4Elfogadva286ms22680 KiB
5Elfogadva284ms22424 KiB
6Hibás válasz287ms22368 KiB
7Elfogadva293ms22420 KiB
8Elfogadva291ms22168 KiB
9Elfogadva300ms22424 KiB
subtask30/23
10Elfogadva1ms508 KiB
11Elfogadva1ms508 KiB
12Hibás válasz1ms316 KiB
13Hibás válasz2ms316 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
subtask40/16
16Hibás válasz2ms316 KiB
17Hibás válasz2ms316 KiB
18Hibás válasz2ms316 KiB
19Hibás válasz2ms316 KiB
20Hibás válasz2ms432 KiB
21Elfogadva3ms316 KiB
22Hibás válasz3ms316 KiB
subtask50/42
23Hibás válasz416ms20840 KiB
24Hibás válasz455ms20832 KiB
25Elfogadva455ms20844 KiB
26Hibás válasz418ms21100 KiB
27Hibás válasz407ms20848 KiB
28Elfogadva402ms20640 KiB
29Hibás válasz423ms21152 KiB