結果
問題 | No.461 三角形はいくつ? |
ユーザー | kuuso1 |
提出日時 | 2016-12-12 01:43:22 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,712 bytes |
コンパイル時間 | 1,093 ms |
コンパイル使用メモリ | 114,776 KB |
実行使用メモリ | 26,516 KB |
最終ジャッジ日時 | 2024-11-29 12:04:18 |
合計ジャッジ時間 | 39,732 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 31 ms
18,176 KB |
testcase_01 | AC | 29 ms
18,432 KB |
testcase_02 | AC | 30 ms
18,432 KB |
testcase_03 | AC | 26 ms
17,792 KB |
testcase_04 | AC | 35 ms
18,688 KB |
testcase_05 | AC | 1,340 ms
19,252 KB |
testcase_06 | AC | 792 ms
19,416 KB |
testcase_07 | AC | 910 ms
19,548 KB |
testcase_08 | AC | 631 ms
19,276 KB |
testcase_09 | AC | 33 ms
18,688 KB |
testcase_10 | AC | 218 ms
18,944 KB |
testcase_11 | AC | 1,081 ms
19,396 KB |
testcase_12 | AC | 490 ms
18,788 KB |
testcase_13 | AC | 1,603 ms
19,588 KB |
testcase_14 | AC | 1,636 ms
19,464 KB |
testcase_15 | AC | 1,585 ms
19,584 KB |
testcase_16 | AC | 1,186 ms
19,436 KB |
testcase_17 | AC | 1,180 ms
19,568 KB |
testcase_18 | AC | 1,793 ms
19,568 KB |
testcase_19 | AC | 1,719 ms
19,444 KB |
testcase_20 | AC | 1,556 ms
19,608 KB |
testcase_21 | AC | 1,645 ms
19,604 KB |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | AC | 37 ms
19,432 KB |
testcase_26 | AC | 39 ms
19,308 KB |
testcase_27 | AC | 2,681 ms
19,552 KB |
testcase_28 | AC | 37 ms
19,428 KB |
testcase_29 | AC | 390 ms
19,564 KB |
testcase_30 | AC | 199 ms
19,436 KB |
testcase_31 | AC | 730 ms
19,572 KB |
testcase_32 | AC | 931 ms
19,436 KB |
testcase_33 | AC | 37 ms
19,416 KB |
testcase_34 | AC | 35 ms
19,548 KB |
testcase_35 | AC | 36 ms
19,668 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(); //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; } } long tria = l+1; if(h < uh){ l = 0; r = Bottom.Count; while(r-l>1){ c = (r+l)/2; if(Bottom[c] < h){ l = c; }else{ r = c; } } if(l+1 < Bottom.Count && Bottom[l+1].CompareTo(h) == 0) tria--; } //Console.WriteLine("le:{0},re:{1},tria;{2}",le,re,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_){ 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 Red(new Q(a.Num*b.Den+a.Den*b.Num,a.Den*b.Den)); } public static Q operator-(Q a,Q b){ return Red(new Q(a.Num*b.Den-a.Den*b.Num,a.Den*b.Den)); } public static Q operator-(Q a){ return Red(new Q(-a.Num,a.Den)); } public static Q operator*(Q a,Q b){ return Red(new Q(a.Num*b.Num,a.Den*b.Den)); } public static Q operator/(Q a,Q b){ return Red(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 Q Min(Q a,Q b){ return a < b ? a : b; } public override String ToString(){ return this.Num.ToString()+"/"+this.Den.ToString(); } }