結果
問題 | No.202 1円玉投げ |
ユーザー | syoken_desuka |
提出日時 | 2015-05-04 00:50:55 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 16,980 bytes |
コンパイル時間 | 4,622 ms |
コンパイル使用メモリ | 114,972 KB |
実行使用メモリ | 60,484 KB |
最終ジャッジ日時 | 2024-12-22 07:56:28 |
合計ジャッジ時間 | 150,271 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | TLE | - |
testcase_02 | AC | 30 ms
47,744 KB |
testcase_03 | AC | 31 ms
48,080 KB |
testcase_04 | AC | 30 ms
47,948 KB |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | AC | 3,142 ms
56,960 KB |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | AC | 33 ms
21,244 KB |
testcase_23 | AC | 351 ms
21,244 KB |
testcase_24 | AC | 503 ms
21,200 KB |
testcase_25 | AC | 366 ms
21,200 KB |
testcase_26 | AC | 248 ms
21,212 KB |
testcase_27 | AC | 225 ms
21,108 KB |
testcase_28 | AC | 43 ms
21,076 KB |
testcase_29 | AC | 401 ms
21,336 KB |
testcase_30 | AC | 201 ms
21,248 KB |
testcase_31 | AC | 138 ms
21,592 KB |
testcase_32 | AC | 199 ms
21,376 KB |
testcase_33 | AC | 1,099 ms
21,096 KB |
testcase_34 | AC | 72 ms
21,200 KB |
testcase_35 | TLE | - |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
testcase_38 | TLE | - |
testcase_39 | AC | 34 ms
20,992 KB |
testcase_40 | AC | 32 ms
49,536 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
#region ZIPPERusing System;using System.Collections.Generic;using System.Collections;using System.Linq;using System.Text;using sc = Scanner;using ci = CharInterpreter;using System.Numerics;//using Geometry;//using gl = Geometry.GeometryLibrary;using grl = GraphLibrary;class Program{static void Main(string[] args){Solver solver = new Solver();solver.Solve();#if DEBUGSystem.Console.WriteLine("続行するには何かキーを押してください...");System.Console.ReadKey();#endif}}/// <summary>/// 標準入力読み取り支援,自作(某最速の人を参考)/// </summary>#endregion ZIPPERpublic class Solver{#region IGNORE_MEpublic Solver(){//こんすとらくたん きにしなくてよろしい}#endregion IGNORE_MEpublic int MOD = 1000000007;//10^9 + 7public void Solve(){int n = sc.NextInt();int[][] xy = new int[n][];for (int i = 0; i < n; i++){xy[i] = sc.NextIntArray();}HashSet<int>[] hash = new HashSet<int>[20001];for (int i = 0; i < hash.Length; i++){hash[i] = new HashSet<int>();}int ans = 0;for (int i = 0; i < n; i++){bool canSet = true;for (int j = Math.Max(0, xy[i][0] - 20); j <= xy[i][0] + 20 && j <=20000; j++){if (hash[j].Count != 0){for (int k = Math.Min(0,xy[i][1] - 20); k <= xy[i][1] + 20 && k <=20000; k++){if (hash[j].Contains(k)){if ((xy[i][0] - j)*(xy[i][0] - j) + (xy[i][1] - k)*(xy[i][1] - k) < 400 ){canSet = false;j = xy[i][0] + 20 + 10;k = xy[i][0] + 20 + 10;}}}}}if (canSet){hash[xy[i][0]].Add(xy[i][1]);ans++;}}Console.WriteLine(ans);#if DEBUGConsole.WriteLine("t");//local check#endif}}public static class GraphLibrary{public struct Edge{public int From;public int To;public int Cost;public Edge(int from, int to, int cost){this.From = from;this.To = to;this.Cost = cost;}}public class Graph{public List<Edge>[] G;/// <summary>/// 頂点のインデックスは 0 ~ v-1;/// </summary>/// <param name="v">頂点数</param>public Graph(int v){G = new List<Edge>[v];for (int i = 0; i < G.Length; i++){G[i] = new List<Edge>();}}public void AddEdge(Edge edge){G[edge.From].Add(edge);}}#region UTILITYstatic bool IsInfinity(int a){return a == int.MaxValue;}#endregion UTILITY/// <summary>/// 最短経路長を求める/// </summary>/// <param name="v">点の数</param>/// <param name="s">始点 0 ~ v-1</param>/// <param name="ed">辺の情報</param>/// <returns>d[i]: sからiへの最短経路長</returns>public static int[] BellmanFord(int v, int s, Edge[] ed){int[] d = new int[v];for (int i = 0; i < v; i++) d[i] = int.MaxValue;d[s] = 0;while (true){bool update = false;for (int i = 0; i < ed.Length; i++){Edge e = ed[i];if (!IsInfinity(d[e.From]) && !IsInfinity(e.Cost) && d[e.To] > d[e.From] + e.Cost){d[e.To] = d[e.From] + e.Cost;update = true;}}if (!update) break;}return d;}/// <summary>/// 負の閉路が存在するかどうか/// </summary>/// <param name="v">頂点の数</param>/// <param name="ed">辺の集合</param>/// <returns>負の閉路が存在するかどうか</returns>public static bool DoesHaveNegativeLoop(int v, Edge[] ed){int[] d = new int[v];for (int i = 0; i < v; i++){for (int j = 0; j < ed.Length; j++){Edge e = ed[j];if (d[e.To] > d[e.From] + e.Cost){d[e.To] = d[e.From] + e.Cost;if (i == v - 1) return true;//この時の更新があったら閉路があるらしい}}}return false;}/// <summary>/// 負の閉路がある場合、無視できるかどうか/// </summary>/// <param name="v"></param>/// <param name="s"></param>/// <param name="ed"></param>/// <returns></returns>public static bool CanIgnoreNegativeLoop(int v, int s, Edge[] ed){Edge[] connectedNodesChecker = new Edge[ed.Length];for (int i = 0; i < ed.Length; i++){connectedNodesChecker[i] = new Edge(ed[i].From, ed[i].To, 1);}int[] d = BellmanFord(v, s, connectedNodesChecker);HashSet<int> canReachNodesFromS = new HashSet<int>();for (int i = 0; i < v; i++)if (!IsInfinity(d[i]))canReachNodesFromS.Add(i);for (int i = 0; i < ed.Length; i++)if (canReachNodesFromS.Contains(ed[i].From)) connectedNodesChecker[i].Cost = ed[i].Cost;return DoesHaveNegativeLoop(v,connectedNodesChecker);}/// <summary>/// 最短経路長を求める/// </summary>/// <param name="graph">二次元マップ</param>/// <returns>d[i][j]]: iからjへの最短経路長</returns>public static int[][] WarshallFloyd(int[][] graph){int[][] d = new int[graph.Length][];for (int i = 0; i < d.Length; i++) d[i] = new int[graph[0].Length];for (int k = 0; k < graph.Length; k++){for (int i = 0; i < graph.Length; i++){for (int j = 0; j < graph.Length; j++){if (!IsInfinity(d[i][k]) && !IsInfinity(d[k][j])){d[i][j] = Math.Min(d[i][j], d[i][k] + d[k][j]);}}}}return d;}/// <summary>/// 連結なグラフの最小全域木を求める/// </summary>/// <param name="v">頂点の数</param>/// <param name="ed">辺の集合 to, from は気にしなくてよい</param>/// <returns>最小全域木の重み</returns>public static int Kruskal(int v, Edge[] ed){Array.Sort(ed, (a, b) => { return a.Cost - b.Cost; });UnionFindTree uf = new UnionFindTree(v);int res = 0;for (int i = 0; i < ed.Length; i++){Edge e = ed[i];if (!uf.Same(e.To, e.From)){uf.Unite(e.To, e.From);res += e.Cost;}}return res;}#region SUPPORT_INNER_CLASS/// <summary>/// ダイクストラ法に使うつもりの優先度付きキュー/// インナークラス/// </summary>class PriorityQueueForGL{int[] array;int count = 0;Comparison<int> comparison;// <param name="comparison">intに対する比較方向を示すデリゲート, (a,b)のとき返り値intに a_int - b_int (a > b) なら昇順,逆なら降順</param>public void SetOptionData(Comparison<int> comparison, int MaxCount){this.comparison = comparison;array = new int[MaxCount];count = 0;}/// <summary>/// ヒープ化されている配列リストに新しい要素を追加する。/// </summary>/// <param name="array">対象の配列リスト</param>private void PushHeap(int elem){int n = count;count++;array[n] = elem;while (n != 0){int i = (n - 1) / 2;// 親と値を入れ替えif (comparison(array[n], array[i]) < 0){int tmp = array[n]; array[n] = array[i]; array[i] = tmp;}n = i;}}/// <summary>/// ヒープから指定した値を削除する。/// </summary>/// <param name="array">対象の配列リスト</param>private int PopHeap(){if (count == 0)throw new IndexOutOfRangeException("要素が0のキューに要素を取り出す命令がおこなわれました");int n = count - 1;int returnItem = (int)array[0];array[0] = array[n];array[n] = 0;count--;for (int i = 0, j; (j = 2 * i + 1) < n; ){// 値の大きい方の子を選ぶif ((j != n - 1) && (comparison((int)array[j], (int)array[j + 1]) > 0))j++;// 子と値を入れ替えif (comparison((int)array[i], (int)array[j]) > 0){int tmp = (int)array[j]; array[j] = array[i]; array[i] = tmp;}i = j;}return returnItem;}/// <summary>/// 要素のプッシュ./// </summary>/// <param name="elem">挿入したい要素</param>public void Push(int elem){PushHeap(elem);}/// <summary>/// 要素をポップ.出したデータはコレクションの中から消える/// </summary>/// <returns></returns>public int Pop(){return PopHeap();}/// <summary>/// 要素を全て消去する/// </summary>public void Clear(){for (int i = 0; i < array.Length; i++) array[i] = 0;}}/// <summary>/// UF木、蟻本より/// </summary>class UnionFindTree{int[] Par;int[] Rank;/// <summary>/// nの要素数を管理するUF木/// </summary>/// <param name="n"></param>public UnionFindTree(int n){this.Par = new int[n];this.Rank = new int[n];for (int i = 0; i < n; i++){Par[i] = i;}}/// <summary>/// 木の根を求める/// </summary>/// <param name="x"></param>/// <returns></returns>private int Find(int x){if (Par[x] == x)return x;else{Par[x] = Find(Par[x]);return Par[x];}}/// <summary>/// xとyの属する集合を併合/// </summary>/// <param name="x"></param>/// <param name="y"></param>public void Unite(int x, int y){x = Find(x);y = Find(y);if (x == y) return;if (Rank[x] < Rank[y]){Par[x] = y;}else{Par[y] = x;if (Rank[x] == Rank[y]) Rank[x]++;}}/// <summary>/// xとyが同じ集合に属するか否か/// </summary>/// <param name="x"></param>/// <param name="y"></param>/// <returns></returns>public bool Same(int x, int y){return Find(x) == Find(y);}}#endregion SUPPORT_INNER_CLASS}#region STANDARD_READERpublic static class Scanner{public static string NextString(){string tmp = "";while (true){int readData;string data;readData = Console.Read();if (readData == -1) //EOF{break;}data = char.ConvertFromUtf32(readData);if (data == " " || data == "\n"){break;}tmp += data;}return tmp;}public static int NextInt(){string tmp = "";while (true){int readData;string data;readData = Console.Read();if (readData == -1) //EOF{break;}data = char.ConvertFromUtf32(readData);if (data == " " || data == "\n"){break;}tmp += data;}return int.Parse(tmp);}public static long NextLong(){string tmp = "";while (true){int readData;string data;readData = Console.Read();if (readData == -1) //EOF{break;}data = char.ConvertFromUtf32(readData);if (data == " " || data == "\n"){break;}tmp += data;}return long.Parse(tmp);}public static double NextDouble(){string tmp = "";while (true){int readData;string data;readData = Console.Read();if (readData == -1) //EOF{break;}data = char.ConvertFromUtf32(readData);if (data == " " || data == "\n"){break;}tmp += data;}return double.Parse(tmp);}public static string[] NextStrArray(){return Console.ReadLine().Split(' ');}public static int[] NextIntArray(){string[] s = NextStrArray();int[] a = new int[s.Length];for (int i = 0; i < a.Length; i++){a[i] = int.Parse(s[i]);}return a;}public static long[] NextLongArray(){string[] s = NextStrArray();long[] a = new long[s.Length];for (int i = 0; i < a.Length; i++){a[i] = long.Parse(s[i]);}return a;}public static double[] NextDoubleArray(){string[] s = NextStrArray();double[] a = new double[s.Length];for (int i = 0; i < a.Length; i++){a[i] = double.Parse(s[i]);}return a;}}/// <summary>/// 二次元グリッドなどの文字列で与えられたマップなどで、/// 手軽にデータ変換を適用するためのクラス/// </summary>public static class CharInterpreter{/// <summary>/// 変換用辞書/// </summary>private static Dictionary<char, int> MapToInt = new Dictionary<char, int>();/// <summary>/// 変換法則を追加する/// </summary>/// <param name="c">char文字</param>/// <param name="i">対応する整数値</param>public static void AddCorrespondence(char c,int i){MapToInt.Add(c,i);}/// <summary>/// 文字列に対して、対応付けされた/// 例外処理をしていないので注意/// </summary>/// <returns>対応対応がなかった場合はバグる;;</returns>public static int Inquiry(char c){int ret = 0;MapToInt.TryGetValue(c, out ret);return ret;}/// <summary>/// 指定された変換法則の元でint[,]の二次元平面を生成する/// 対応関係がない場合の例外処理をしていないので注意/// </summary>/// <param name="field">配列の各文字列の長さが全て同じでないとうまく作動しないので注意</param>/// <returns> int[ field.length , field[0].length]型の配列 </returns>public static int[,] GenerateSquareField(string[] field){int[,] ret = new int[field.Length, field[0].Length];for (int i = 0; i < field.Length; i++){for (int j = 0; j < field[0].Length; j++){MapToInt.TryGetValue(field[i][j], out ret[i, j]);}}return ret;}}#endregion STANDARD_READER