結果
| 問題 | No.5009 Draw A Convex Polygon |
| ユーザー |
 yuimyo
|
| 提出日時 | 2022-12-09 02:44:53 |
| 言語 | C# (.NET 8.0.203) |
| 結果 |
AC
|
| 実行時間 | 370 ms / 2,600 ms |
| コード長 | 19,953 bytes |
| コンパイル時間 | 7,762 ms |
| 実行使用メモリ | 63,216 KB |
| スコア | 208,944 |
| 平均クエリ数 | 208945.00 |
| 最終ジャッジ日時 | 2022-12-09 02:45:05 |
| 合計ジャッジ時間 | 9,429 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
コンパイルメッセージ
Determining projects to restore... Restored /home/judge/data/code/main.csproj (in 121 ms). .NET 向け Microsoft (R) Build Engine バージョン 17.0.0-preview-21470-01+cb055d28f Copyright (C) Microsoft Corporation.All rights reserved. プレビュー版の .NET を使用しています。https://aka.ms/dotnet-core-preview をご覧ください main -> /home/judge/data/code/bin/Release/net6.0/main.dll main -> /home/judge/data/code/bin/Release/net6.0/publish/
ソースコード
using CPlibs;
using Kzrnm.Competitive.IO;
using System;
using System.Buffers.Text;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
namespace AdventCalendarContest2022.Problems
{
internal partial class ProblemB
{
static void Solve()
{
Solver1();
cw.Flush();
}
static void Solver1()
{
// (10, 0), (9, 1), (8, 2), ..., (0, 10), (-1, 9)
// 10_0_-10_0_
// 0_10_0_-10_
// (0~1000000)*2 - 1000000
// M(M+1)/2*2-M = (M+1)(M-1)=M^2-1
// 2*10^9+1 = M^2-1 (Nは非負)とおくと M=√(2*10^9+2)=44721.359...
var X = new List<long>();
var Y = new List<long>();
int N = -1;
int M = 52236;// l + (r - l) / 2;// 44721; // 250000
X.Clear();
Y.Clear();
X.Add(0);
Y.Add(0);
for (long dx = M; dx > -M; dx--) X.Add(X.Last() + getMnD(M, dx));
for (long dx = -M; dx < M; dx++) X.Add(X.Last() + getMnD(M, dx));
for (long dy = 0; dy < M; dy++) Y.Add(Y.Last() + getMnD(M, dy));
for (long dy = M; dy > -M; dy--) Y.Add(Y.Last() + getMnD(M, dy));
for (long dy = -M; dy < 0; dy++) Y.Add(Y.Last() + getMnD(M, dy));
var cen = X.Min() + (X.Max() - X.Min()) / 2;
N = X.Count() - 1; // 最後は含まない
for (int i = 0; i < N; i++)
{
X[i] -= cen;
Y[i] -= 1000000000L;
}
cw.WriteLine(N);
for (int i = 0; i < N; i++)
cw.WriteLine($"{X[i]} {Y[i]}");
// cw.WriteLine($"({X.Min()},{X.Max()}),({Y.Min()},{Y.Max()})");
cw.Flush();
}
static long getMnD(int M, long d)
{
long p = Math.Abs(d);
long q = M - p;
return d / Algo.Gcd(p, q);
}
}
}
#region Dependency resolution
namespace AdventCalendarContest2022.Problems
{
internal partial class ProblemB
{
static ConsoleReader cr;
static ConsoleWriter cw;
#if COMPETITIVE
public ProblemB(string outputFilePath = null, bool solving = true)
#else
static void Main(string[] args)
#endif
{
#if COMPETITIVE
SourceExpander.Expander.Expand(outputFilePath: outputFilePath);
#endif
if (cw != null)
cw.Dispose();
cr = new ConsoleReader();
cw = new ConsoleWriter();
#if COMPETITIVE
if (solving)
#endif
Solve();
cw.Dispose();
}
}
}
#endregion
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace Kzrnm.Competitive.IO{using static Utf8Parser;using _R=ConsoleReader;using MI=System.Runtime.CompilerServices.MethodImplAttribute;public class ConsoleReader{internal const int BufSize=1<<12;internal readonly Stream input;internal readonly Encoding encoding;internal readonly byte[]buf;internal int pos;internal int len;[MI(256)]public ConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding,BufSize){}[MI(256)]public ConsoleReader(Stream input,Encoding encoding):this(input,encoding,BufSize){}[MI(256)]public ConsoleReader(Stream input,Encoding encoding,int bufferSize){this.input=input;this.encoding=encoding;buf=new byte[bufferSize];}[MI(256)]private void FillEntireNumber(){if((uint)pos>=(uint)buf.Length)FillNextBuffer();while(buf[pos]<=' ')if( ++pos>=len)FillNextBuffer();if(pos+21>=buf.Length&&buf[buf.Length-1]>' ')FillEntireNumberImpl();}private void FillEntireNumberImpl(){buf.AsSpan(pos,len-pos).CopyTo(buf);len-=pos;pos=0;var numberOfBytes=input.Read(buf,len,buf.Length-len);if(numberOfBytes==0)buf[len++]=10;else if(numberOfBytes+len<buf.Length)buf[buf.Length-1]=10;len+=numberOfBytes;}private void FillNextBuffer(){if((len=input.Read(buf,0,buf.Length))==0){buf[0]=10;len=1;}else if(len<buf.Length)buf[buf.Length-1]=10;pos=0;}[MI(256)]internal byte ReadByte(){if(pos>=len)FillNextBuffer();return buf[pos++];}[MI(256)]public T Read<T>(){if(typeof(T)==typeof(int))return(T)(object)Int();if(typeof(T)==typeof(uint))return(T)(object)UInt();if(typeof(T)==typeof(long))return(T)(object)Long();if(typeof(T)==typeof(ulong))return(T)(object)ULong();if(typeof(T)==typeof(double))return(T)(object)Double();if(typeof(T)==typeof(decimal))return(T)(object)Decimal();if(typeof(T)==typeof(char))return(T)(object)Char();if(typeof(T)==typeof(string))return(T)(object)Ascii();return Throw<T>();}static T Throw<T>()=>throw new NotSupportedException(typeof(T).Name);[MI(256)]public int Int(){FillEntireNumber();TryParse(buf.AsSpan(pos),out int v,out int bc);pos+=bc;return v;}[MI(256)]public uint UInt(){FillEntireNumber();TryParse(buf.AsSpan(pos),out uint v,out int bc);pos+=bc;return v;}[MI(256)]public long Long(){FillEntireNumber();TryParse(buf.AsSpan(pos),out long v,out int bc);pos+=bc;return v;}[MI(256)]public ulong ULong(){FillEntireNumber();TryParse(buf.AsSpan(pos),out ulong v,out int bc);pos+=bc;return v;}[MI(256)]public double Double(){FillEntireNumber();TryParse(buf.AsSpan(pos),out double v,out int bc);pos+=bc;return v;}[MI(256)]public decimal Decimal(){FillEntireNumber();TryParse(buf.AsSpan(pos),out decimal v,out int bc);pos+=bc;return v;}[MI(256)]public string String(){var sb=new List<byte>();;byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(' '<b);return encoding.GetString(sb.ToArray());}[MI(256)]public string Ascii(){var sb=new StringBuilder();byte b;do b=ReadByte();while(b<=' ');do{sb.Append((char)b);b=ReadByte();}while(' '<b);return sb.ToString();}[MI(256)]public string Line(){var sb=new List<byte>();byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}[MI(256)]public char Char(){byte b;do b=ReadByte();while(b<=' ');return(char)b;}[MI(256)]public int Int0()=>Int()-1;[MI(256)]public uint UInt0()=>UInt()-1;[MI(256)]public long Long0()=>Long()-1;[MI(256)]public ulong ULong0()=>ULong()-1;[MI(256)]public static implicit operator int(_R cr)=>cr.Int();[MI(256)]public static implicit operator uint(_R cr)=>cr.UInt();[MI(256)]public static implicit operator long(_R cr)=>cr.Long();[MI(256)]public static implicit operator ulong(_R cr)=>cr.ULong();[MI(256)]public static implicit operator double(_R cr)=>cr.Double();[MI(256)]public static implicit operator decimal(_R cr)=>cr.Decimal();[MI(256)]public static implicit operator string(_R cr)=>cr.Ascii();public T[]Repeat<T>(int count){var arr=new T[count];for(int i=0;i<arr.Length;i++)arr[i]=Read<T>();return arr;}}}
namespace Kzrnm.Competitive.IO{using _W=ConsoleWriter;using MI=System.Runtime.CompilerServices.MethodImplAttribute;public sealed partial class ConsoleWriter:IDisposable{private const int BufSize=1<<12;private readonly StreamWriter sw;public StreamWriter StreamWriter=>sw;public ConsoleWriter():this(Console.OpenStandardOutput(),Console.OutputEncoding){}public ConsoleWriter(Stream output,Encoding encoding):this(output,encoding,BufSize){}public ConsoleWriter(Stream output,Encoding encoding,int bufferSize){sw=new StreamWriter(output,encoding,bufferSize);}[MI(256)]public void Flush()=>sw.Flush();[MI(256)]public void Dispose()=>Flush();[MI(256)]public _W Write<T>(T v){sw.Write(v.ToString());return this;}[MI(256)]public _W WriteLine(){sw.WriteLine();return this;}[MI(256)]public _W WriteLine<T>(T v){sw.WriteLine(v.ToString());return this;}[MI(256)]public _W WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);[MI(256)]public _W WriteLineJoin<T1,T2>((T1,T2)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2);[MI(256)]public _W WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3);[MI(256)]public _W WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3,tuple.Item4);[MI(256)]public _W WriteLineJoin<TTuple>(TTuple tuple)where TTuple:System.Runtime.CompilerServices.ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++)col[i]=tuple[i];return WriteLineJoin(col);}[MI(256)]public _W WriteLineJoin(params object[]col)=>WriteMany(' ',col);[MI(256)]public _W WriteLineJoin<T1,T2>(T1 v1,T2 v2){sw.Write(v1.ToString());sw.Write(' ');sw.WriteLine(v2.ToString());return this;}[MI(256)]public _W WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){sw.Write(v1.ToString());sw.Write(' ');sw.Write(v2.ToString());sw.Write(' ');sw.WriteLine(v3.ToString());return this;}[MI(256)]public _W WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){sw.Write(v1.ToString());sw.Write(' ');sw.Write(v2.ToString());sw.Write(' ');sw.Write(v3.ToString());sw.Write(' ');sw.WriteLine(v4.ToString());return this;}[MI(256)]public _W WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);[MI(256)]public _W WriteGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}[MI(256)]public _W WriteGrid<TTuple>(IEnumerable<TTuple>tuples)where TTuple:System.Runtime.CompilerServices.ITuple{foreach(var tup in tuples)WriteLineJoin(tup);return this;}[MI(256)]private _W WriteMany<T>(char sep,IEnumerable<T>col){var en=col.GetEnumerator();if(!en.MoveNext())goto End;sw.Write(en.Current.ToString());while(en.MoveNext()){sw.Write(sep);sw.Write(en.Current.ToString());}End:sw.WriteLine();return this;}}}
namespace Kzrnm.Competitive.IO{using MI=System.Runtime.CompilerServices.MethodImplAttribute;public partial class ConsoleWriter{[MI(256)]public ConsoleWriter WriteLine(ReadOnlySpan<char>v){sw.WriteLine(v);return this;}[MI(256)]public ConsoleWriter WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);[MI(256)]public ConsoleWriter WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);[MI(256)]public ConsoleWriter WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[MI(256)]public ConsoleWriter WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);[MI(256)]private ConsoleWriter WriteMany<T>(char sep,ReadOnlySpan<T>col){var en=col.GetEnumerator();if(!en.MoveNext())return this;sw.Write(en.Current.ToString());while(en.MoveNext()){sw.Write(sep);sw.Write(en.Current.ToString());}sw.WriteLine();return this;}}}
namespace CPlibs { using MI = System.Runtime.CompilerServices.MethodImplAttribute; public static class Algo { [MI(256)] public static Dictionary<int, int> Prime(int n) { var primes = new Dictionary<int, int>(); for (int i = 2; i * i <= n; i++) { while (true) { if (n % i == 0) { if (!primes.ContainsKey(i)) primes[i] = 0; primes[i]++; n /= i; } else break; } } if (n > 1) { if (!primes.ContainsKey(n)) primes[n] = 0; primes[n]++; } return primes; } [MI(256)] public static Dictionary<long, long> Prime(long n) { var primes = new Dictionary<long, long>(); for (int i = 2; i * i <= n; i++) { while (true) { if (n % i == 0) { if (!primes.ContainsKey(i)) primes[i] = 0; primes[i]++; n /= i; } else break; } } if (n > 1) { if (!primes.ContainsKey(n)) primes[n] = 0; primes[n]++; } return primes; } [MI(256)] public static bool[] SieveOfEratosthenes(int n) { var isPrime = Calc.Init1dArray<bool>(n + 1, true); isPrime[1] = true; for (int p = 2; p <= n; p++) { if (!isPrime[p]) continue; for (int q = p * 2; q <= n; q += p) isPrime[q] = true; } return isPrime; } [MI(256)] public static bool[] SieveOfEratosthenes(int n, out int[] minFactors) { var isPrime = Calc.Init1dArray<bool>(n + 1, true); isPrime[1] = true; minFactors = Calc.Init1dArray<int>(n + 1, -1); minFactors[1] = 1; for (int p = 2; p <= n; p++) { if (!isPrime[p]) continue; minFactors[p] = p; for (int q = p * 2; q <= n; q += p) { isPrime[q] = true; if (minFactors[q] == -1) minFactors[q] = p; } } return isPrime; } [MI(256)] public static int[] TopologicalSortTarjan(List<int>[] graph) { var size = graph.Length; var answers = new List<int>(); var visiteds = new bool[size]; for (int i = 0; i < size; i++) topologicalSortTarjanVisit(i, graph, visiteds, answers); answers.Reverse(); return answers.ToArray(); } [MI(256)] private static void topologicalSortTarjanVisit(int u, List<int>[] graph, bool[] visiteds, List<int> answers) { if (!visiteds[u]) { visiteds[u] = true; foreach (var v in graph[u]) topologicalSortTarjanVisit(v, graph, visiteds, answers); answers.Add(u); } } [MI(256)] public static (char Ch, int Count)[] RLE(string str) { var res = new List<(char, int)>(); var prev = 'ω'; var cnt = 0; for (int i = 0; i < str.Length; i++) { var c = str[i]; if (i > 0 && prev != c) { res.Add((prev, cnt)); cnt = 0; } prev = c; cnt++; } res.Add((prev, cnt)); return res.ToArray(); } public static int[] CoordCompression(int[] coords) { var n = coords.Length; var comp = new int[n]; { var temp = new HashSet<int>(coords).ToArray(); Array.Sort(temp); for (int i = 0; i < n; i++) comp[i] = Algo.BinarySearch(-1, temp.Count() - 1, m => coords[i] <= temp[m]).Right; } return comp; } public static int[] CoordCompression(long[] coords, bool hasRight = false) { var n = coords.Length; var comp = new int[n]; { var temp = new HashSet<long>(coords); if (hasRight) { for (int i = 0; i < n; i++) temp.Add(coords[i] + 1); } var temp2 = temp.ToArray(); Array.Sort(temp2); for (int i = 0; i < n; i++) comp[i] = Algo.BinarySearch(-1, temp2.Count() - 1, m => coords[i] <= temp2[m]).Right; } return comp; } [MI(256)] [Obsolete] public static int nHr(int n, int r) => CombinationRep(n, r); [MI(256)] [Obsolete] public static int nCr(int n, int r) => Combination(n, r); [MI(256)] public static int CombinationRep(int n, int r) => Combination(n + r - 1, r); [MI(256)] public static int Combination(int n, int r) { var res = 1; for (int i = n; i >= n - r + 1; i--) res *= i; for (int i = r; i >= 1; i--) res /= i; return res; } [MI(256)] public static long GcdAll(params long[] values) { if (values.Length == 0) throw new ArgumentException(); var x = values[0]; for (int i = 1; i < values.Length; i++) x = Gcd(x, values[i]); return x; } [MI(256)] public static long Gcd(long a, long b) { if (b == 0) return a; return Gcd(b, a % b); } public static Dictionary<char, int> CntChar(this string str) { var res = new Dictionary<char, int>(); for (int i = 0; i < str.Length; i++) { if (!res.ContainsKey(str[i])) res[str[i]] = 0; res[str[i]]++; } return res; } [MI(256)] public static (int Left, int Right) BinarySearch(int left, int right, Func<int, bool> condition) { while (right - left > 1) { var mid = left + (right - left) / 2; if (condition(mid)) right = mid; else left = mid; } return (left, right); } [MI(256)] public static (long Left, long Right) BinarySearch(long left, long right, Func<long, bool> condition) { while (right - left > 1) { var mid = left + (right - left) / 2; if (condition(mid)) right = mid; else left = mid; } return (left, right); } [MI(256)] public static double TernarySearch(Func<double, double> f, double low, double high, int n = 500) { while (n-- >= 0) { double c1 = (low * 2 + high) / 3; double c2 = (low + high * 2) / 3; if (f(c1) > f(c2)) low = c1; else high = c2; } return low; } [MI(256)] public static int[] EulerTourEdge(int size, int[][] treeGraph, int root) { if (size != treeGraph.Length) throw new ArgumentException($"size != graph.Length"); var res = new List<int>(); eulerTourEdgeDfs(treeGraph, new bool[size], res, new int[size], new int[size], 0); return res.ToArray(); } [MI(256)] public static int[] EulerTourEdge(int size, int[][] treeGraph, int root, out int[] edgeIn, out int[] edgeOut) { if (size != treeGraph.Length) throw new ArgumentException($"size != graph.Length"); edgeIn = new int[size]; edgeOut = new int[size]; var res = new List<int>(); eulerTourEdgeDfs(treeGraph, new bool[size], res, edgeIn, edgeOut, 0); return res.ToArray(); } [MI(256)] public static int[] EulerTourEdge(int size, List<int>[] treeGraph, int root) { if (size != treeGraph.Length) throw new ArgumentException($"size != graph.Length"); var res = new List<int>(); eulerTourEdgeDfs(treeGraph, new bool[size], res, new int[size], new int[size], 0); return res.ToArray(); } [MI(256)] public static int[] EulerTourEdge(int size, List<int>[] treeGraph, int root, out int[] edgeIn, out int[] edgeOut) { if (size != treeGraph.Length) throw new ArgumentException($"size != graph.Length"); edgeIn = new int[size]; edgeOut = new int[size]; var res = new List<int>(); eulerTourEdgeDfs(treeGraph, new bool[size], res, edgeIn, edgeOut, 0); return res.ToArray(); } [MI(256)] static void eulerTourEdgeDfs(List<int>[] treeGraph, bool[] visited, List<int> res, int[] edgeIn, int[] edgeOut, int from) { visited[from] = true; res.Add(+(from + 1)); edgeIn[from] = res.Count - 1; foreach (var to in treeGraph[from]) { if (visited[to]) continue; visited[to] = true; eulerTourEdgeDfs(treeGraph, visited, res, edgeIn, edgeOut, to); } res.Add(-(from + 1)); edgeOut[from] = res.Count - 1; } [MI(256)] static void eulerTourEdgeDfs(int[][] treeGraph, bool[] visited, List<int> res, int[] edgeIn, int[] edgeOut, int from) { visited[from] = true; res.Add(+(from + 1)); edgeIn[from] = res.Count - 1; foreach (var to in treeGraph[from]) { if (visited[to]) continue; visited[to] = true; eulerTourEdgeDfs(treeGraph, visited, res, edgeIn, edgeOut, to); } res.Add(-(from + 1)); edgeOut[from] = res.Count - 1; } } }
namespace CPlibs { using MI = System.Runtime.CompilerServices.MethodImplAttribute; public static class Calc { [MI(256)] public static void Swap<T>(ref T value1, ref T value2) { var temp = value1; value1 = value2; value2 = temp; } [MI(256)] public static bool Range(int value, int min, int max) { return min <= value && value <= max; } [MI(256)] public static bool Range(long value, long min, long max) { return min <= value && value <= max; } [MI(256)] public static long CeilDiv(long x, long y) { return (x + (y - 1)) / y; } [MI(256)] public static long Clamp(long value, long min, long max) { return Math.Min(Math.Max(value, min), max); } [MI(256)] public static long Xor(params long[] values) { if (values.Length == 0) return 0; long xored = values[0]; for (int i = 1; i < values.Length; i++) xored ^= values[i]; return xored; } [MI(256)] public static bool Chmin<T>(ref T value1, params T[] valuesMany) where T : IComparable<T> { bool swapped = false; foreach (var value2 in valuesMany) if (value1.CompareTo(value2) > 0) { swapped = true; value1 = value2; } return swapped; } [MI(256)] public static bool Chmax<T>(ref T value1, params T[] valuesMany) where T : IComparable<T> { bool swapped = false; foreach (var value2 in valuesMany) if (value1.CompareTo(value2) < 0) { swapped = true; value1 = value2; } return swapped; } [MI(256)] public static T[] Init1dArray<T>(int x, T initialValue = default(T)) { var res = new T[x]; for (int i = 0; i < x; i++) res[i] = initialValue; return res; } [MI(256)] public static T[][] Init2dArray<T>(int x, int y, T initialValue = default(T)) { var res = new T[x][]; for (int i = 0; i < x; i++) { res[i] = new T[y]; for (int j = 0; j < y; j++) res[i][j] = initialValue; } return res; } [MI(256)] public static T[][][] Init3dArray<T>(int x, int y, int z, T initialValue = default(T)) { var res = new T[x][][]; for (int i = 0; i < x; i++) { res[i] = new T[y][]; for (int j = 0; j < y; j++) { res[i][j] = new T[z]; for (int k = 0; k < z; k++) res[i][j][k] = initialValue; } } return res; } [MI(256)] public static T[][][][] Init4dArray<T>(int x, int y, int z, int w, T initialValue = default(T)) { var res = new T[x][][][]; for (int i = 0; i < x; i++) { res[i] = new T[y][][]; for (int j = 0; j < y; j++) { res[i][j] = new T[z][]; for (int k = 0; k < z; k++) { res[i][j][k] = new T[w]; for (int l = 0; l < w; l++) { res[i][j][k][l] = initialValue; } } } } return res; } } }
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander