結果
問題 | No.461 三角形はいくつ? |
ユーザー | Grenache |
提出日時 | 2016-12-12 19:00:50 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 715 ms / 5,000 ms |
コード長 | 6,617 bytes |
コンパイル時間 | 4,825 ms |
コンパイル使用メモリ | 84,304 KB |
実行使用メモリ | 57,516 KB |
最終ジャッジ日時 | 2023-08-19 21:14:02 |
合計ジャッジ時間 | 24,662 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge10 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
49,764 KB |
testcase_01 | AC | 45 ms
49,616 KB |
testcase_02 | AC | 44 ms
49,584 KB |
testcase_03 | AC | 45 ms
49,924 KB |
testcase_04 | AC | 82 ms
51,588 KB |
testcase_05 | AC | 615 ms
55,496 KB |
testcase_06 | AC | 409 ms
54,976 KB |
testcase_07 | AC | 495 ms
55,916 KB |
testcase_08 | AC | 410 ms
55,712 KB |
testcase_09 | AC | 66 ms
51,352 KB |
testcase_10 | AC | 252 ms
54,992 KB |
testcase_11 | AC | 520 ms
55,232 KB |
testcase_12 | AC | 354 ms
55,452 KB |
testcase_13 | AC | 674 ms
55,076 KB |
testcase_14 | AC | 674 ms
55,452 KB |
testcase_15 | AC | 649 ms
55,380 KB |
testcase_16 | AC | 246 ms
54,900 KB |
testcase_17 | AC | 243 ms
54,744 KB |
testcase_18 | AC | 540 ms
54,736 KB |
testcase_19 | AC | 614 ms
54,968 KB |
testcase_20 | AC | 680 ms
55,764 KB |
testcase_21 | AC | 684 ms
55,088 KB |
testcase_22 | AC | 715 ms
55,616 KB |
testcase_23 | AC | 382 ms
54,696 KB |
testcase_24 | AC | 405 ms
55,604 KB |
testcase_25 | AC | 266 ms
54,556 KB |
testcase_26 | AC | 268 ms
54,792 KB |
testcase_27 | AC | 293 ms
55,056 KB |
testcase_28 | AC | 267 ms
54,896 KB |
testcase_29 | AC | 498 ms
55,376 KB |
testcase_30 | AC | 450 ms
55,340 KB |
testcase_31 | AC | 564 ms
55,548 KB |
testcase_32 | AC | 585 ms
55,644 KB |
testcase_33 | AC | 106 ms
53,396 KB |
testcase_34 | AC | 96 ms
53,348 KB |
testcase_35 | AC | 108 ms
53,372 KB |
testcase_36 | AC | 456 ms
55,988 KB |
testcase_37 | AC | 456 ms
55,824 KB |
testcase_38 | AC | 454 ms
55,700 KB |
testcase_39 | AC | 452 ms
57,516 KB |
testcase_40 | AC | 456 ms
56,096 KB |
testcase_41 | AC | 465 ms
55,700 KB |
testcase_42 | AC | 689 ms
55,732 KB |
testcase_43 | AC | 695 ms
55,476 KB |
testcase_44 | AC | 621 ms
55,776 KB |
ソースコード
import java.io.*; import java.util.*; public class Main_yukicoder461 { private static Scanner sc; private static Printer pr; private static void solve() { int n = sc.nextInt(); List<List<Pair>> ab = new ArrayList<>(); for (int i = 0; i < 3; i++) { ab.add(new ArrayList<>()); } for (int i = 0; i < n; i++) { int p = sc.nextInt(); int a = sc.nextInt(); int b = sc.nextInt(); ab.get(p).add(new Pair(a, a + b)); } for (int i = 0; i < 3; i++) { ab.get(i).add(new Pair(1, 1)); Collections.sort(ab.get(i)); } long ret = 0; for (int i = 0; i < 3; i++) { ret += ab.get(i).size(); // pr.printf("%d %d\n", i, ab.get(i).size()); ret += cnt(ab.get(i), ab.get((i - 1 + 3) % 3)); // pr.printf("%d %d\n", i, cnt(ab.get(i), ab.get((i - 1 + 3) % 3))); ret += cnt(ab.get(i), ab.get((i + 1) % 3)); // pr.printf("%d %d\n", i, cnt(ab.get(i), ab.get((i + 1) % 3))); } Pair e1b = new Pair(0, 0); Pair e2b = new Pair(0, 0); for (int i = 0; i < 3; i++) { for (Pair e1 : ab.get((i + 1) % 3)) { e1b.a = e1.ab - e1.a; e1b.ab = e1.ab; if (e1b.a == 0) { continue; } for (Pair e2 : ab.get((i + 2) % 3)) { e2b.a = e2.ab - e2.a; e2b.ab = e2.ab; if (e2b.a == 0) { continue; } ret += cnt2(e1b, e2b, ab.get(i)); } } } // pr.println(ret); pr.println(ret / 3); } private static int cnt(List<Pair> l1, List<Pair> l2) { int ret = 0; int n = l1.size(); // Pair tmp = new Pair(0, 0); for (Pair e2 : l2) { tmp.a = e2.ab - e2.a; tmp.ab = e2.ab; if (tmp.a == 0) { continue; } int index = Collections.binarySearch(l1, tmp); if (index >= 0) { ret += n - (index + 1); } else { index = -(index + 1); ret += n - index; } } return ret; } private static Pair tmp = new Pair(0, 0); private static Pair tmpone = new Pair(1, 1); private static int cnt2(Pair e1b, Pair e2b, List<Pair> l) { int ret = 0; int n = l.size(); if (n == 0) { return 0; } tmp.a = e1b.a * e2b.ab + e2b.a * e1b.ab; tmp.ab = e1b.ab * e2b.ab; if (tmp.compareTo(tmpone) > 0) { return 0; } Pair max; if (e1b.compareTo(e2b) > 0) { max = e1b; } else { max = e2b; } int index = Collections.binarySearch(l, tmp); if (index >= 0) { ret += n - (index + 1); } else { index = -(index + 1); ret += n - index; } int index2 = Collections.binarySearch(l, max); if (index2 >= 0) { ret += index - index2; } else { index2 = -(index2 + 1); ret += index - index2; } // if (tmp.compareTo(tmpone) < 0) { // ret++; // } return ret; } private static class Pair implements Comparable<Pair> { long a; long ab; Pair(long a, long ab) { this.a = a; this.ab = ab; } @Override public int compareTo(Pair o) { // return Long.compare(a * (o.a + o.b), o.a * (a + b)); return Long.compare(a * o.ab, o.a * ab); } } // --------------------------------------------------- public static void main(String[] args) { sc = new Scanner(System.in); pr = new Printer(System.out); solve(); pr.close(); sc.close(); } @SuppressWarnings("unused") private static class Scanner { BufferedReader br; Scanner (InputStream in) { br = new BufferedReader(new InputStreamReader(in)); } private boolean isPrintable(int ch) { return ch >= '!' && ch <= '~'; } private boolean isCRLF(int ch) { return ch == '\n' || ch == '\r' || ch == -1; } private int nextPrintable() { try { int ch; while (!isPrintable(ch = br.read())) { if (ch == -1) { throw new NoSuchElementException(); } } return ch; } catch (IOException e) { throw new NoSuchElementException(); } } String next() { try { int ch = nextPrintable(); StringBuilder sb = new StringBuilder(); do { sb.appendCodePoint(ch); } while (isPrintable(ch = br.read())); return sb.toString(); } catch (IOException e) { throw new NoSuchElementException(); } } int nextInt() { try { // parseInt from Integer.parseInt() boolean negative = false; int res = 0; int limit = -Integer.MAX_VALUE; int radix = 10; int fc = nextPrintable(); if (fc < '0') { if (fc == '-') { negative = true; limit = Integer.MIN_VALUE; } else if (fc != '+') { throw new NumberFormatException(); } fc = br.read(); } int multmin = limit / radix; int ch = fc; do { int digit = ch - '0'; if (digit < 0 || digit >= radix) { throw new NumberFormatException(); } if (res < multmin) { throw new NumberFormatException(); } res *= radix; if (res < limit + digit) { throw new NumberFormatException(); } res -= digit; } while (isPrintable(ch = br.read())); return negative ? res : -res; } catch (IOException e) { throw new NoSuchElementException(); } } long nextLong() { try { // parseLong from Long.parseLong() boolean negative = false; long res = 0; long limit = -Long.MAX_VALUE; int radix = 10; int fc = nextPrintable(); if (fc < '0') { if (fc == '-') { negative = true; limit = Long.MIN_VALUE; } else if (fc != '+') { throw new NumberFormatException(); } fc = br.read(); } long multmin = limit / radix; int ch = fc; do { int digit = ch - '0'; if (digit < 0 || digit >= radix) { throw new NumberFormatException(); } if (res < multmin) { throw new NumberFormatException(); } res *= radix; if (res < limit + digit) { throw new NumberFormatException(); } res -= digit; } while (isPrintable(ch = br.read())); return negative ? res : -res; } catch (IOException e) { throw new NoSuchElementException(); } } float nextFloat() { return Float.parseFloat(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine() { try { int ch; while (isCRLF(ch = br.read())) { if (ch == -1) { throw new NoSuchElementException(); } } StringBuilder sb = new StringBuilder(); do { sb.appendCodePoint(ch); } while (!isCRLF(ch = br.read())); return sb.toString(); } catch (IOException e) { throw new NoSuchElementException(); } } void close() { try { br.close(); } catch (IOException e) { // throw new NoSuchElementException(); } } } private static class Printer extends PrintWriter { Printer(PrintStream out) { super(out); } } }