結果

問題 No.202 1円玉投げ
ユーザー syoken_desukasyoken_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.

ソースコード

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

#region ZIPPER
using 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 DEBUG
System.Console.WriteLine("");
System.Console.ReadKey();
#endif
}
}
/// <summary>
///
/// </summary>
#endregion ZIPPER
public class Solver
{
#region IGNORE_ME
public Solver()
{
// 
}
#endregion IGNORE_ME
public int MOD = 1000000007;//10^9 + 7
public 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 DEBUG
Console.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 UTILITY
static 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]: si</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]]: ij</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>
/// nUF
/// </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>
/// xy
/// </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>
/// xy
/// </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_READER
public 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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0