Last active
December 24, 2016 18:04
-
-
Save hamadu/55cdb08a1a9b0ff361eeb358669214f9 to your computer and use it in GitHub Desktop.
Wunder Fund 2016-F : Double Knapsack
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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