結果
問題 | No.461 三角形はいくつ? |
ユーザー | りあん |
提出日時 | 2016-12-09 13:31:19 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,179 ms / 5,000 ms |
コード長 | 3,550 bytes |
コンパイル時間 | 1,228 ms |
コンパイル使用メモリ | 119,656 KB |
実行使用メモリ | 29,308 KB |
最終ジャッジ日時 | 2024-05-06 18:29:17 |
合計ジャッジ時間 | 16,964 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 32 ms
25,112 KB |
testcase_01 | AC | 31 ms
25,492 KB |
testcase_02 | AC | 31 ms
27,528 KB |
testcase_03 | AC | 26 ms
23,732 KB |
testcase_04 | AC | 33 ms
25,260 KB |
testcase_05 | AC | 581 ms
27,208 KB |
testcase_06 | AC | 337 ms
25,236 KB |
testcase_07 | AC | 394 ms
25,388 KB |
testcase_08 | AC | 279 ms
29,308 KB |
testcase_09 | AC | 32 ms
25,112 KB |
testcase_10 | AC | 105 ms
27,228 KB |
testcase_11 | AC | 449 ms
25,132 KB |
testcase_12 | AC | 215 ms
25,352 KB |
testcase_13 | AC | 643 ms
23,220 KB |
testcase_14 | AC | 619 ms
27,152 KB |
testcase_15 | AC | 653 ms
25,360 KB |
testcase_16 | AC | 62 ms
25,100 KB |
testcase_17 | AC | 60 ms
25,368 KB |
testcase_18 | AC | 1,179 ms
23,092 KB |
testcase_19 | AC | 1,178 ms
25,108 KB |
testcase_20 | AC | 644 ms
27,212 KB |
testcase_21 | AC | 671 ms
27,336 KB |
testcase_22 | AC | 661 ms
25,360 KB |
testcase_23 | AC | 135 ms
27,148 KB |
testcase_24 | AC | 131 ms
27,260 KB |
testcase_25 | AC | 40 ms
27,404 KB |
testcase_26 | AC | 40 ms
25,344 KB |
testcase_27 | AC | 40 ms
27,052 KB |
testcase_28 | AC | 40 ms
25,396 KB |
testcase_29 | AC | 280 ms
21,304 KB |
testcase_30 | AC | 150 ms
25,136 KB |
testcase_31 | AC | 501 ms
25,364 KB |
testcase_32 | AC | 664 ms
25,400 KB |
testcase_33 | AC | 39 ms
25,264 KB |
testcase_34 | AC | 38 ms
25,260 KB |
testcase_35 | AC | 39 ms
27,176 KB |
testcase_36 | AC | 216 ms
27,404 KB |
testcase_37 | AC | 207 ms
25,136 KB |
testcase_38 | AC | 217 ms
27,076 KB |
testcase_39 | AC | 194 ms
25,352 KB |
testcase_40 | AC | 207 ms
25,136 KB |
testcase_41 | AC | 220 ms
27,212 KB |
testcase_42 | AC | 591 ms
25,288 KB |
testcase_43 | AC | 603 ms
25,364 KB |
testcase_44 | AC | 587 ms
27,208 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Linq; using System.Linq.Expressions; using System.IO; class Program { static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; static Scan sc = new Scan(); static void Main() { int n = sc.Int; var lines = new List<long[]>[3]; for (int i = 0; i < 3; i++) { lines[i] = new List<long[]>(); lines[i].Add(new long[]{ 0, 1 }); } for (int i = 0; i < n; i++) { var a = sc.IntArr; var g = mymath.gcd(a[1], a[2]); lines[a[0]].Add(new long[]{ a[2] / g, (a[1] + a[2]) / g }); } for (int i = 0; i < 3; i++) lines[i].Sort((x, y) => (x[0] * y[1]).CompareTo(y[0] * x[1])); if (lines[0].Count > lines[2].Count) swap(ref lines[0], ref lines[2]); if (lines[1].Count > lines[2].Count) swap(ref lines[1], ref lines[2]); long ans = 0; foreach (var a in lines[0]) { foreach (var b in lines[1]) { if (!okay(a, b)) continue; long s = a[0] * b[1] + a[1] * b[0], t = a[1] * b[1]; var g = mymath.gcd(s, t); s /= g; t /= g; int ok = 0, ng = lines[2].Count; while (ok < ng - 1) { int m = (ok + ng) >> 1; var c = lines[2][m]; if (okay(a, c) && okay(b, c)) ok = m; else ng = m; } ans += ok + 1; long u = t - s; int l = 0, r = lines[2].Count - 1; while (true) { int m = (l + r) >> 1; var c = lines[2][m]; if (t * c[0] == u * c[1]) { --ans; break; } if (l >= r) break; if (t * c[0] < u * c[1]) l = m + 1; else r = m - 1; } } } sw.WriteLine(ans); sw.Flush(); } static bool okay(long[] a, long[] b) => a[0] * b[1] + a[1] * b[0] <= a[1] * b[1]; static void swap<T>(ref T a, ref T b) { var t = a; a = b; b = t; } static void DBG<T>(params T[] a) => Console.WriteLine(string.Join(" ", a)); static void DBG(params object[] a) => Console.WriteLine(string.Join(" ", a)); } class Scan { public int Int => int.Parse(Str); public long Long => long.Parse(Str); public double Double => double.Parse(Str); public string Str => Console.ReadLine().Trim(); public int[] IntArr => StrArr.Select(int.Parse).ToArray(); public long[] LongArr => StrArr.Select(long.Parse).ToArray(); public double[] DoubleArr => StrArr.Select(double.Parse).ToArray(); public string[] StrArr => Str.Split(); } class mymath { public static long gcd(long a, long b) { while (b > 0) { var t = a % b; a = b; b = t; } return a; } // a x + b y = gcd(a, b) public static long extgcd(long a, long b, out long x, out long y) { long g = a; x = 1; y = 0; if (b > 0) { g = extgcd(b, a % b, out y, out x); y -= a / b * x; } return g; } public static long lcm(long a, long b) => a / gcd(a, b) * b; }