結果
問題 | No.461 三角形はいくつ? |
ユーザー |
![]() |
提出日時 | 2016-12-15 13:52:24 |
言語 | D (dmd 2.109.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,091 bytes |
コンパイル時間 | 1,746 ms |
コンパイル使用メモリ | 153,508 KB |
実行使用メモリ | 11,608 KB |
最終ジャッジ日時 | 2024-06-12 05:37:09 |
合計ジャッジ時間 | 8,203 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 1 TLE * 1 -- * 39 |
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/numeric.d(2999): Warning: cannot inline function `std.numeric.gcdImpl!ulong.gcdImpl`
ソースコード
import std.algorithm;import std.array;import std.ascii;import std.container;import std.conv;import std.math;import std.numeric;import std.range;import std.stdio;import std.string;import std.typecons;void log(A...)(A arg) { stderr.writeln(arg); }int size(T)(in T s) { return cast(int)s.length; }long lcm(long a, long b) {return a / gcd(a, b) * b;}int sign(long x) { return x == 0 ? 0 : cast(int)(x / abs(x)); }struct Rational {long n, d; // numerator, denominator;this(long n, long d) {if (d < 0) {n *= -1;d *= -1;}long g = gcd(abs(n), d);this.n = n / g;this.d = d / g;}this(long n) {this(n, 1);}Rational opBinary(string op)(in Rational x) const if (op == "+" || op == "-") {long nd = lcm(d, x.d);long nn = mixin("n * (nd / d)" ~ op ~ "x.n * (nd / x.d)");return Rational(nn, nd);}Rational opBinary(string op)(real k) const if (op == "*" || op == "/") {return Rational(mixin("n" ~ op ~ "k"), d);}int opCmp(in Rational x) const {return (this - x).n.sign;}}struct P { long a, b; }void main() {auto N = readln.chomp.to!int;auto S = new P[][3];foreach (i; 0 .. N) {int p; long a, b; readf("%s %s %s\n",&p, &a, &b);S[p] ~= P(a, b);}foreach (p; 0 .. 3) S[p] ~= P(1, 0);Rational[] Z;foreach (s; S[0]) {Z ~= Rational(s.a, s.a + s.b);}sort(Z);long ans = 0;bool[Rational] exist;foreach (z; Z) exist[z] = true;foreach (x; S[1]) {foreach (y; S[2]) {auto s = Rational(x.a, x.a + x.b);auto t = Rational(y.a, y.a + y.b);if (! (s + t >= Rational(1)) ) continue;auto lb = Rational(1) - min(s, t);auto mid = Rational(1) - (s + t - Rational(1));auto sZ = Z.assumeSorted;ans += sZ.lowerBound(mid).length - sZ.lowerBound(lb).length;ans += sZ.upperBound(mid).length;}}writeln(ans);}