結果

問題 No.461 三角形はいくつ?
ユーザー izuru_matsuura
提出日時 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`

ソースコード

diff #
プレゼンテーションモードにする

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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0