結果
問題 | No.461 三角形はいくつ? |
ユーザー | kuuso1 |
提出日時 | 2016-12-12 02:46:23 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,364 bytes |
コンパイル時間 | 2,390 ms |
コンパイル使用メモリ | 117,080 KB |
実行使用メモリ | 36,660 KB |
最終ジャッジ日時 | 2024-11-29 13:23:59 |
合計ジャッジ時間 | 51,636 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
20,224 KB |
testcase_01 | AC | 35 ms
20,352 KB |
testcase_02 | AC | 36 ms
20,352 KB |
testcase_03 | AC | 32 ms
20,096 KB |
testcase_04 | AC | 41 ms
20,096 KB |
testcase_05 | AC | 1,649 ms
24,564 KB |
testcase_06 | AC | 995 ms
24,564 KB |
testcase_07 | AC | 1,141 ms
24,560 KB |
testcase_08 | AC | 797 ms
24,556 KB |
testcase_09 | AC | 39 ms
20,352 KB |
testcase_10 | AC | 270 ms
24,448 KB |
testcase_11 | AC | 1,362 ms
24,560 KB |
testcase_12 | AC | 606 ms
24,284 KB |
testcase_13 | AC | 1,964 ms
24,424 KB |
testcase_14 | AC | 2,005 ms
24,300 KB |
testcase_15 | AC | 1,952 ms
24,432 KB |
testcase_16 | AC | 1,330 ms
21,708 KB |
testcase_17 | AC | 1,284 ms
21,608 KB |
testcase_18 | AC | 2,557 ms
24,428 KB |
testcase_19 | AC | 2,449 ms
24,564 KB |
testcase_20 | AC | 1,912 ms
24,560 KB |
testcase_21 | AC | 2,024 ms
24,428 KB |
testcase_22 | AC | 1,999 ms
24,580 KB |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | AC | 45 ms
21,540 KB |
testcase_26 | AC | 45 ms
21,668 KB |
testcase_27 | AC | 4,853 ms
24,408 KB |
testcase_28 | AC | 45 ms
21,540 KB |
testcase_29 | AC | 549 ms
24,548 KB |
testcase_30 | AC | 278 ms
24,440 KB |
testcase_31 | AC | 1,054 ms
24,576 KB |
testcase_32 | AC | 1,367 ms
24,312 KB |
testcase_33 | AC | 43 ms
21,408 KB |
testcase_34 | AC | 41 ms
21,488 KB |
testcase_35 | AC | 41 ms
21,628 KB |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | WA | - |
コンパイルメッセージ
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; using System.Collections.Generic; using System.Linq; using System.Text; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ List<Q> Bottom = new List<Q>(); List<Q> L = new List<Q>(); List<Q> R = new List<Q>(); Bottom.Add(new Q(0,1+0)); L.Add(new Q(1,1+0)); R.Add(new Q(1,1+0)); for(int i=0;i<N;i++){ if(P[i] == 0){ Bottom.Add(new Q(B[i],(A[i]+B[i]))); }else if(P[i] == 1){ L.Add(new Q(A[i],B[i]+A[i])); }else{ R.Add(new Q(A[i],B[i]+A[i])); } } Bottom.Sort(); HashSet<Q> BH = new HashSet<Q>(); foreach(var lb in Bottom)BH.Add(lb); //Console.WriteLine(String.Join(" ",Bottom)); long ans = 0; foreach(var le in L){ foreach(var re in R){ var h = le - (1 - re); if(h < 0) continue; var uh = Q.Min(le,re); int l = 0; int r = Bottom.Count; int c = 0; while(r-l>1){ c = (r+l)/2; if(Bottom[c] < uh){ l = c; }else{ r = c; } } //Console.WriteLine("{0}.Contained? {1}",h,BH.Contains(h)); long tria = 0; if(h == 0){ tria = l; if(BH.Contains(uh)) tria++; }else if(h == uh){ tria = l+1; }else{ tria = l+1; if(BH.Contains(h)){ tria--; } } //Console.WriteLine("le:{0},re:{1},h:{2},uh,{3},tria;{4}",le,re,h,uh,tria); ans += tria; } } Console.WriteLine(ans); } int N; long[] P,A,B; public Sol(){ N = ri(); P = new long[N]; A = new long[N]; B = new long[N]; for(int i=0;i<N;i++){ var d = rla(); P[i] = d[0]; A[i] = d[1]; B[i] = d[2]; } } static String rs(){return Console.ReadLine();} static int ri(){return int.Parse(Console.ReadLine());} static long rl(){return long.Parse(Console.ReadLine());} static double rd(){return double.Parse(Console.ReadLine());} static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);} static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));} static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));} static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));} } struct Q:IComparable<Q> { long num; long den; public static long gcd(long a,long b){ return a==0?b:gcd(b%a,a); } public static Q Red(Q x){ long n=x.Num; long d=x.Den; long g=gcd(Math.Abs(n),Math.Abs(d)); n/=g; d/=g; if(d<0){n*=-1;d*=-1;} return new Q(n,d); } public int CompareTo(Q t){ var d = num*t.den-den*t.num; return d > 0 ? 1 : d < 0 ? -1 : 0; } public long Num{ get{return num;} set{this.num=value;} } public long Den{ get{return den;} set{this.den=value;} } public Q(long n_,long d_){ if(d_<0){ n_*=-1;d_*=-1;} long g=gcd(Math.Abs(n_),Math.Abs(d_)); n_/=g; d_/=g; num=n_;den=d_; } public static implicit operator Q(long n){ return new Q(n,1); } public static Q operator+(Q a,Q b){ return (new Q(a.Num*b.Den+a.Den*b.Num,a.Den*b.Den)); } public static Q operator-(Q a,Q b){ return (new Q(a.Num*b.Den-a.Den*b.Num,a.Den*b.Den)); } public static Q operator-(Q a){ return (new Q(-a.Num,a.Den)); } public static Q operator*(Q a,Q b){ return (new Q(a.Num*b.Num,a.Den*b.Den)); } public static Q operator/(Q a,Q b){ return (new Q(a.Num*b.Den,a.Den*b.Num)); } public static bool operator>(Q a,Q b){ return a.CompareTo(b) > 0; } public static bool operator<(Q a,Q b){ return a.CompareTo(b) < 0; } public static bool operator>=(Q a,Q b){ return a.CompareTo(b) >= 0; } public static bool operator<=(Q a,Q b){ return a.CompareTo(b) <= 0; } public static bool operator==(Q a,Q b){ return a.Equals(b); } public static bool operator!=(Q a,Q b){ return !(a==b); } public override bool Equals(System.Object obj){ if(obj == null) return false; Q p = (Q) obj; if((System.Object) p == null ) return false; return den * p.num == num * p.den; } public override int GetHashCode(){ long g = gcd(Math.Abs(den),Math.Abs(num)); long d = den/g; long n = num/g; return (d^n).GetHashCode(); } public static Q Min(Q a,Q b){ return a < b ? a : b; } public override String ToString(){ return this.Num.ToString()+"/"+this.Den.ToString(); } }