Create a gist now

Instantly share code, notes, and snippets.

@hamadu /F.java
Last active Dec 24, 2016

Wunder Fund 2016-F : Double Knapsack
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class F {
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
int n = in.nextInt();
long[] a = new long[n];
long[] b = new long[n];
for (int i = 0; i < n ; i++) {
a[i] = in.nextInt();
}
for (int i = 0; i < n ; i++) {
b[i] = in.nextInt();
}
long sumA = 0;
long sumB = 0;
for (int i = 0; i < n ; i++) {
sumA += a[i];
sumB += b[i];
}
int[] segments = sumA <= sumB ? solve(a, b) : solve(b, a);
int fromA = segments[0];
int toA = segments[1];
int fromB = segments[2];
int toB = segments[3];
if (sumA > sumB) {
fromA = segments[2];
toA = segments[3];
fromB = segments[0];
toB = segments[1];
}
String lineA = buildIntegers(fromA, toA);
String lineB = buildIntegers(fromB, toB);
out.println(toA - fromA + 1);
out.println(lineA);
out.println(toB - fromB + 1);
out.println(lineB);
out.flush();
}
private static int[] solve(long[] a, long[] b) {
// Σa <= Σb
int[] diffA = new int[1000010];
int[] diffB = new int[1000010];
Arrays.fill(diffA, -2);
Arrays.fill(diffB, -2);
diffA[0] = -1;
diffB[0] = -1;
int n = a.length;
int fromA = -1;
int toA = -1;
int fromB = -1;
int toB = -1;
int bi = 0;
long asum = 0, bsum = 0;
for (int i = 0 ; i < n ; i++) {
asum += a[i];
// asumを超えないように足せるだけ足す
while (bi < n && bsum + b[bi] <= asum) {
bsum += b[bi];
bi++;
}
// 差分はd (0 <= d <= n-1)
int d = (int)(asum - bsum);
// すでに差がdになるペアを見つけてたら終了。鳩の巣原理よりこのif文はどこかで真になる
if (diffA[d] != -2) {
fromA = diffA[d]+1;
toA = i;
fromB = diffB[d]+1;
toB = bi-1;
break;
}
   // 差がdになるペアを記憶
diffA[d] = i;
diffB[d] = bi-1;
}
return new int[]{fromA, toA, fromB, toB};
}
private static String buildIntegers(int fromA, int toA) {
StringBuilder line = new StringBuilder();
for (int i = fromA ; i <= toA ; i++) {
line.append(' ').append(i+1);
}
return line.substring(1);
}
// 以下テンプレにつき略
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment