文档章节

CodeForces - 618F Double Knapsack

o
 osc_x4h57ch8
发布于 2018/04/24 11:44
字数 599
阅读 14
收藏 0

精选30+云产品,助力企业轻松上云!>>>

Discription

You are given two multisets A and B. Each multiset has exactly n integers each between 1 and n inclusive. Multisets may contain multiple copies of the same number.

You would like to find a nonempty subset of A and a nonempty subset of B such that the sum of elements in these subsets are equal. Subsets are also multisets, i.e. they can contain elements with equal values.

If no solution exists, print  - 1. Otherwise, print the indices of elements in any such subsets of A and B that have the same sum.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 1 000 000) — the size of both multisets.

The second line contains n integers, denoting the elements of A. Each element will be between 1 and n inclusive.

The third line contains n integers, denoting the elements of B. Each element will be between 1 and n inclusive.

Output

If there is no solution, print a single integer  - 1. Otherwise, your solution should be printed on four lines.

The first line should contain a single integer ka, the size of the corresponding subset of A. The second line should contain ka distinct integers, the indices of the subset of A.

The third line should contain a single integer kb, the size of the corresponding subset of B. The fourth line should contain kb distinct integers, the indices of the subset of B.

Elements in both sets are numbered from 1 to n. If there are multiple possible solutions, print any of them.

Examples

Input
10
10 10 10 10 10 10 10 10 10 10
10 9 8 7 6 5 4 3 2 1
Output
1
2
3
5 8 10
Input
5
4 4 3 3 3
2 2 2 2 5
Output
2
2 3
2
3 5


一道神构造。
设sa[]为a[]的前缀和,sb[]为b的前缀和,对于每个0<=i<=n,我们找到一个最大的使得sb[j]<=sa[i]的j,这样每个sa[i]-sb[j]都是[0,n-1]的整数了(因为如果sa[i]-sb[j]>=n的话,j可以继续后移(a[],b[]中元素都<=n))
所以至少会有一对 i和i'满足 sa[i]-sb[j] == sa[i']-sb[j'],直接输出就行了。。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1000005;
ll a[maxn],b[maxn];
int px[maxn],py[maxn],n;
inline int read(){
	int x=0; char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x;
}
void W(int x){ if(x>=10) W(x/10); putchar(x%10+'0');}
int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read(),a[i]+=a[i-1];
	for(int i=1;i<=n;i++) b[i]=read(),b[i]+=b[i-1];
	for(int i=0,j=0,D;i<=n;i++){
		for(;j<n&&b[j+1]<=a[i];j++);
		D=a[i]-b[j];
		if(px[D]){
			W(i-px[D]+1),puts("");
			for(int o=px[D];o<=i;o++) W(o),putchar(' ');
			puts(""),W(j-py[D]+1),puts("");
			for(int o=py[D];o<=j;o++) W(o),putchar(' ');
			return 0;
		}
		px[D]=i+1,py[D]=j+1;
	}
	return 0;
}

  

 
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【CF618F】Double Knapsack(构造)

【CF618F】Double Knapsack(构造) 题面 洛谷Codeforces 题解 很妙的一道题。发现找两个数集很不爽,我们强制加强限制,我们来找两个区间,使得他们的区间和相等。把区间和转为前缀和的形式...

osc_kfnbvkb9
2019/03/21
2
0
codeforces618f Double Knapsack【抽屉原理】

解题思路: 真是道非常妙的构造。 不妨设总和小的是集合A。 我们把集合看成数组,对两个数组各求前缀和(包括0号位置); 那么对于每个 ,必然存在一个 ,使得 ,设为 ,可以发现 随 单调增。...

cdsszjj
2017/12/28
0
0
[codeforces 618 F] Double Knapsack (抽屉原理)

题目链接:http://codeforces.com/contest/618/problem/F 题目: 题目大意: 有两个大小为 N 的可重集 A, B, 每个元素都在 1 到 N 之间. 分别找出 A 和 B 的一个子集, 使得这两个子集元素之和...

osc_v22siqak
2018/08/25
2
0
HPSocket运行一段时间后,随机报错,具体信息如下

问题签名: 问题事件名称: APPCRASH 应用程序名: HBNetMonitorServer.exe 应用程序版本: 1.0.0.0 应用程序时间戳: 57173440 故障模块名称: HPSocket4C_U.dll 故障模块版本: 3.3.2.0 故障模块时...

xiguoxing
2016/04/26
790
2
CF1132.Educational Codeforces Round 61(简单题解)

A .Regular Bracket Sequence 题意:给定“((” , “()” , “)(”, “))”四种,问是否可以组成合法括号匹配 思路:设四种是ABCD,B可以不用管,而C在A或者D存在时可以不考虑,然后就是A...

osc_eul3o28k
2019/03/06
3
0

没有更多内容

加载失败,请刷新页面

加载更多

等到所有jQuery Ajax请求都完成了吗? - Wait until all jQuery Ajax requests are done?

问题: How do I make a function wait until all jQuery Ajax requests are done inside another function? 我如何让一个函数等到所有jQuery Ajax请求都在另一个函数中完成之后? In short...

富含淀粉
14分钟前
0
0
OSChina 周日乱弹 —— 那么长的绳子,你这是放风筝呢

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @ 巴拉迪维:黑豹乐队的单曲《无地自容》 耳畔突然响起旋律,是那首老歌。中国摇滚有了《一无所有》不再一无所有;中国摇滚有了《无地自容》不...

小小编辑
今天
65
1
《吐血整理》-顶级程序员书单集

你知道的越多,你不知道的越多 给岁月以文明,而不是给文明以岁月 前言 王潇:格局决定了一个人的梦想,梦想反过来决定行为。 那格局是什么呢? 格局是你能够看见的深度、广度和密度。 王潇认...

敖丙
2019/12/11
11
0
我可以在Android版式中加下划线吗? - Can I underline text in an Android layout?

问题: 如何在Android布局xml文件中定义带下划线的文本? 解决方案: 参考一: https://stackoom.com/question/A31z/我可以在Android版式中加下划线吗 参考二: https://oldbug.net/q/A31z/...

法国红酒甜
今天
26
0
干掉ELK | 使用Prometheus+Grafana搭建监控平台

什么是Prometheus? Prometheus是由SoundCloud开发的开源监控报警系统和时序列数据库(TSDB)。Prometheus使用Go语言开发,是Google BorgMon监控系统的开源版本。 Prometheus的特点 · 多维度...

木九天
今天
34
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部