結果
| 問題 | No.246 質問と回答 |
| ユーザー |
 ユヅキ
|
| 提出日時 | 2023-06-18 11:49:44 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 110 ms / 2,000 ms |
| コード長 | 24,520 bytes |
| コンパイル時間 | 3,710 ms |
| コンパイル使用メモリ | 122,816 KB |
| 実行使用メモリ | 43,072 KB |
| 平均クエリ数 | 30.87 |
| 最終ジャッジ日時 | 2024-06-26 00:43:55 |
| 合計ジャッジ時間 | 8,706 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
コンパイルメッセージ
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.Diagnostics;using System.Linq;using System.Text;using System.IO;using System.Threading.Tasks;using static System.Console;using static System.Math;using P=System.Tuple<long,long>;namespace Tasks{public class Program{public static void Main(string[] args){var sw = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false};Console.SetOut(sw);new Program().Solve(new ConsoleInput(Console.In, ' '));Console.Out.Flush();}public void Solve(ConsoleInput cin){long ok=0,ng=pow(10,9)+1;long mid=(ok+ng)/2;while(ng-ok>1){Out("? "+mid);Console.Out.Flush();int res=cin.nextint;if(res==1) ok=mid;else if(res==0) ng=mid;mid=(ok+ng)/2;}Out("! "+ok);}public List<List<int>> graph(int n,int m,bool edge=false){List<List<int>> g=new List<List<int>>();for(int i=0;i<n;++i) g.Add(new List<int>());for(int i=0;i<m;++i){var cin =new ConsoleInput(Console.In, ' ');int u=cin.nextint-1,v=cin.nextint-1;g[u].Add(v);if(!edge) g[v].Add(u);}return g;}public static bool inrange(int y, int x, int h, int w) { return 0 <= x && x < w && 0 <= y && y < h; }public static void Out<T>(params T[] A){int n=A.Length;for(int i=0;i<n;++i){if(i!=n-1){if(typeof(T)==typeof(double)){Write("{0:f12}",A[i]);Write(" ");}else Write(A[i]+" ");}else{if(typeof(T)==typeof(double)){WriteLine("{0:f12}",A[i]);}else WriteLine(A[i]);}}}public static void Out(){WriteLine();}public static void Yes(bool ok) => Console.WriteLine(ok ? "Yes": "No");public static void YES(bool ok) => Console.WriteLine(ok ? "YES": "NO");static void chmax(ref long m, long v, long mod = -1) { m = Math.Max(m, v); if (mod != -1) m %= mod; }static void chmax(ref int m, int v) { m = Math.Max(m, v);}static void chmin(ref long m, long v, long mod = -1) { m = Math.Min(m, v); if (mod != -1) m %= mod; }static void chmin(ref int m, int v) { m = Math.Min(m, v);}static void swap<T>(ref T a, ref T b) { var w = a; a = b; b = w; }static void Fill<T>(T[] array, T x) { for (int i = 0; i < array.Length; i++) { array[i] = x; } }static void Fill<T>(T[,] array, T x) { for (int i = 0; i < array.GetLength(0); i++){for (int j = 0; j < array.GetLength(1); j++) array[i, j] = x; }}static void Showarray<T>(T[,] array){for(int i=0;i<array.GetLength(0);i++){for(int j=0;j<array.GetLength(1);j++){Write(array[i,j]+" ");}WriteLine();}}static T[,] Rotatearray<T>(T[,] array) {int h=array.GetLength(0);int w=array.GetLength(1);var array2 = new T[w,h];for (int i = 0; i < h; i++)for (int j = 0; j < w; j++){array2[j,h - i - 1] = array[i, j];}return array2;}public static void OutAllLine<T>(IEnumerable<T> items){var sb = new StringBuilder();foreach (T result in items){sb.Append(result + "\n");}sb = sb.Remove(sb.Length - 1, 1);Console.WriteLine(sb);}public static void OutEachSpace<T>(IEnumerable<T> items){var sb = new StringBuilder();foreach (T result in items){sb.Append(result + " ");}sb = sb.Remove(sb.Length - 1, 1);Console.WriteLine(sb);}static List<T[]> AllPermutation<T>(params T[] array) where T : IComparable{var a = new List<T>(array).ToArray();var res = new List<T[]>();res.Add(new List<T>(a).ToArray());var n = a.Length;var next = true;while (next){next = false;int i;for (i = n - 2; i >= 0; i--){if (a[i].CompareTo(a[i + 1]) < 0) break;}if (i < 0) break;var j = n;do{j--;} while (a[i].CompareTo(a[j]) > 0);if (a[i].CompareTo(a[j]) < 0){var tmp = a[i];a[i] = a[j];a[j] = tmp;Array.Reverse(a, i + 1, n - i - 1);res.Add(new List<T>(a).ToArray());next = true;}}return res;}public static T max<T>(params T[] A) where T : IComparable{int n=A.Length;T max=A[0];for(int i=1;i<n;++i){max=max.CompareTo(A[i]) > 0 ? max:A[i];}return max;}public static T min<T>(params T[] A) where T : IComparable{int n=A.Length;T min=A[0];for(int i=1;i<n;++i){min=min.CompareTo(A[i]) < 0 ? min:A[i];}return min;}static long pow(long a,long n){long ret=1;while(n>0){if((n&1)>0) ret*=a;a=a*a;n>>=1;}return ret;}static long modpow(long a,long n, long mod){long ret=1;while(n>0){if((n&1)>0) ret=ret*a%mod;a=a*a%mod;n>>=1;}return ret;}public static long modinv( long a, long mod ){return modpow(a,mod-2,mod);}static long Lcm(long a, long b){return a / Gcd(a, b) * b;}static long Gcd(long m, long n){if (n == 0) return m;return Gcd(n, m % n);}public static int LowerBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer){int low = start;int high = end;int mid;while (low < high){mid = ((high - low) >> 1) + low;if (comparer.Compare(arr[mid], value) < 0)low = mid + 1;elsehigh = mid;}return low;}public static int LowerBound<T>(T[] arr, T value) where T : IComparable{return LowerBound(arr, 0, arr.Length, value, Comparer<T>.Default);}public static int UpperBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer){int low = start;int high = end;int mid;while (low < high){mid = ((high - low) >> 1) + low;if (comparer.Compare(arr[mid], value) <= 0)low = mid + 1;elsehigh = mid;}return low;}public static int UpperBound<T>(T[] arr, T value){return UpperBound(arr, 0, arr.Length, value, Comparer<T>.Default);}public static Dictionary<long, long> PrimeFactorization(long n){var result = new Dictionary<long, long>();for (long i = 2; i * i <= n; i++){if (n % i != 0) continue;long exponents = 0;while (n % i == 0){exponents++;n /= i;}result[i] = exponents;}if (n != 1) result[n] = 1;return result;}public static bool Isprime(long num){if (num < 2) { return false; }if (num == 2) { return true; }if (num % 2 == 0) { return false; }double sqrtNum = Math.Sqrt(num);for (int i = 3; i <= sqrtNum; i += 2){if (num % i == 0) { return false; }}return true;}public static long[] GetDivisors(long n){HashSet<long> divisors = new HashSet<long>();for (long i = 1; i * i <= n; i++){if (n % i != 0) { continue; }divisors.Add(i);divisors.Add(n / i);}return divisors.OrderBy(x => x).ToArray();}public static bool[] PrimeTable(int n){var prime = new bool[n + 1];for(int i=0;i<=n;i++) prime[i]=true;if (n >= 0) prime[0] = false;if (n >= 1) prime[1] = false;for (int i = 2; i * i <= n; i++){if (!prime[i]) continue;for (int j = i * i; j <= n; j += i) prime[j] = false;}return prime;}static int lis(int[] a){const int inf=(1<<30);int n=a.Length;int[] dp=new int[n+1];Fill(dp,inf);for(int i=0;i<n;++i){int idx=LowerBound(dp,a[i]);dp[idx]=a[i];}int ret=LowerBound(dp,inf);return ret;}static int[,] lcs(char[] s,char[] t){int n=s.Length,m=t.Length;int[,] dp=new int[n+1,m+1];for(int i=0;i<n;++i){for(int j=0;j<m;++j){if(s[i]==t[j]) dp[i+1,j+1]=dp[i,j]+1;else dp[i+1,j+1]=max(dp[i+1,j],dp[i,j+1]);}}return dp;}static long inversionnum(int[] array){int n=array.Length;if(n==0) return 0;int[] copy=new int[n];Array.Copy(array,copy,n);Array.Sort(copy);int[] bit=new int[n+1];long ans=((long)n*(n-1)) >> 1;for(int i=0;i<n;++i){int min=0,max=n;int comp=array[i];while(max-min>1){int mid=(min+max) >> 1;if(copy[mid]<=comp) min=mid;else max=mid;}for(int j=max; j>0;j-=j&-j) ans-=bit[j];for(int j=max;j<n+1;j+=j&-j) ++bit[j];}return ans;}}class Dikstra{public int N { get; }private List<Edge>[] _graph;public Dikstra(int n){N = n;_graph = new List<Edge>[n];for (int i = 0; i < n; i++) _graph[i] = new List<Edge>();}public void Add(int a, int b, long cost = 1)=> _graph[a].Add(new Edge(b, cost));public long[] GetMinCost(int start){var cost = new long[N];for (int i = 0; i < N; i++) cost[i] = ((long)1<<60);cost[start] = 0;var q = new PriorityQueue<Vertex>(isDescending:false);q.Enqueue(new Vertex(start, 0));while (q.Count > 0){var v = q.Dequeue();if (v.cost != cost[v.index]) continue;foreach (var e in _graph[v.index]){if (cost[e.to] > v.cost + e.cost){cost[e.to] = v.cost + e.cost;q.Enqueue(new Vertex(e.to, cost[e.to]));}}}return cost;}public struct Edge{public int to;public long cost;public Edge(int to, long cost){this.to = to;this.cost = cost;}}public struct Vertex : IComparable<Vertex>{public int index;public long cost;public Vertex(int index, long cost){this.index = index;this.cost = cost;}public int CompareTo(Vertex other)=> cost.CompareTo(other.cost);}}class PriorityQueue<T> : IEnumerable<T>{private readonly List<T> _data = new List<T>();private readonly IComparer<T> _comparer;private readonly bool _isDescending;public PriorityQueue(IComparer<T> comparer, bool isDescending = true){_comparer = comparer;_isDescending = isDescending;}public PriorityQueue(Comparison<T> comparison, bool isDescending = true): this(Comparer<T>.Create(comparison), isDescending){}public PriorityQueue(bool isDescending = true): this(Comparer<T>.Default, isDescending){}public void Enqueue(T item){_data.Add(item);var childIndex = _data.Count - 1;while (childIndex > 0){var parentIndex = (childIndex - 1) / 2;if (Compare(_data[childIndex], _data[parentIndex]) >= 0)break;Swap(childIndex, parentIndex);childIndex = parentIndex;}}public T Dequeue(){var lastIndex = _data.Count - 1;var firstItem = _data[0];_data[0] = _data[lastIndex];_data.RemoveAt(lastIndex--);var parentIndex = 0;while (true){var childIndex = parentIndex * 2 + 1;if (childIndex > lastIndex)break;var rightChild = childIndex + 1;if (rightChild <= lastIndex && Compare(_data[rightChild], _data[childIndex]) < 0)childIndex = rightChild;if (Compare(_data[parentIndex], _data[childIndex]) <= 0)break;Swap(parentIndex, childIndex);parentIndex = childIndex;}return firstItem;}public T Peek(){return _data[0];}private void Swap(int a, int b){var tmp = _data[a];_data[a] = _data[b];_data[b] = tmp;}private int Compare(T a, T b){return _isDescending ? _comparer.Compare(b, a) : _comparer.Compare(a, b);}public int Count => _data.Count;public IEnumerator<T> GetEnumerator(){return _data.GetEnumerator();}IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();}class UnionFind{private int[] _unionfind;private int[] _unionfind_size;public UnionFind(int a){_unionfind = new int[a];_unionfind_size = new int[a];for(int i=0;i<a;i++){_unionfind[i] = i;_unionfind_size[i] = 1;}}public int Root(int x){if(_unionfind[x] == x) return x;return _unionfind[x] = Root(_unionfind[x]);}public void Unite(int a,int b){a = Root(a);b = Root(b);if(a == b) return;if(_unionfind_size[a] < _unionfind_size[b]){int temp = a;a = b;b = temp;}_unionfind[b] = a;_unionfind_size[a] += _unionfind_size[b];}public bool Same(int a,int b){return Root(a) == Root(b);}public int Size(int x){return _unionfind_size[Root(x)];}}public class SegmentTree<T>{public int N { get; private set; }private T[] _tree;private readonly Func<T, T, T> _updateMethod;private readonly T _initValue;public SegmentTree(IEnumerable<T> items, Func<T, T, T> updateMethod, T initValue) {T[] array = items.ToArray();_updateMethod = updateMethod;_initValue = initValue;N = 1;while (N < array.Length) N *= 2;_tree = Enumerable.Repeat(initValue, 2 * N - 1).ToArray();for (int i = 0; i < array.Length; i++) _tree[N + i - 1] = array[i];for (int i = N - 2; i >= 0; i--) _tree[i] = _updateMethod(_tree[2 * i + 1], _tree[2 * i + 2]);}public void Update(int i, T x){i = N + i - 1;_tree[i] = x;while(i > 0){i = (i - 1) / 2;_tree[i] = _updateMethod(_tree[2 * i + 1], _tree[2 * i + 2]);}}public T Execute(int a, int b)=> Execute(a, b, 0, 0, N);private T Execute(int a, int b, int k, int l, int r){if (r <= a || b <= l) return _initValue;if (a <= l && r <= b) return _tree[k];var vl = Execute(a, b, 2 * k + 1, l, (l + r) / 2);var vr = Execute(a, b, 2 * k + 2, (l + r) / 2, r);return _updateMethod(vl, vr);}}class Deque<T> : IEnumerable<T>{public T this[int i]{get { return this.Buffer[(this.FirstIndex + i) % this.Capacity]; }set{if (i < 0) throw new ArgumentOutOfRangeException();this.Buffer[(this.FirstIndex + i) % this.Capacity] = value;}}private T[] Buffer;private int Capacity;private int FirstIndex;private int LastIndex{get { return (this.FirstIndex + this.Length) % this.Capacity; }}public int Length;public Deque(int capacity = 16){this.Capacity = capacity;this.Buffer = new T[this.Capacity];this.FirstIndex = 0;}public void PushBack(T data){if (this.Length == this.Capacity) this.Resize();this.Buffer[this.LastIndex] = data;this.Length++;}public void PushFront(T data){if (this.Length == this.Capacity) this.Resize();var index = this.FirstIndex - 1;if (index < 0) index = this.Capacity - 1;this.Buffer[index] = data;this.Length++;this.FirstIndex = index;}public T PopBack(){if (this.Length == 0) throw new InvalidOperationException("There is no data available.");var data = this[this.Length - 1];this.Length--;return data;}public T PopFront(){if (this.Length == 0) throw new InvalidOperationException("There is no data available.");var data = this[0];this.FirstIndex++;this.FirstIndex %= this.Capacity;this.Length--;return data;}private void Resize(){var newArray = new T[this.Capacity * 2];for (int i = 0; i < this.Length; i++){newArray[i] = this[i];}this.FirstIndex = 0;this.Capacity *= 2;this.Buffer = newArray;}public IEnumerator<T> GetEnumerator(){for (int i = 0; i < this.Length; i++){yield return this[i];}}IEnumerator IEnumerable.GetEnumerator(){for (int i = 0; i < this.Length; i++){yield return this[i];}}}public class ConsoleInput{private readonly System.IO.TextReader _stream;private char _separator = ' ';private Queue<string> inputStream;public ConsoleInput(System.IO.TextReader stream, char separator = ' '){this._separator = separator;this._stream = stream;inputStream = new Queue<string>();}public string Read{get{if (inputStream.Count != 0) return inputStream.Dequeue();string[] tmp = _stream.ReadLine().Split(_separator);for (int i = 0; i < tmp.Length; ++i)inputStream.Enqueue(tmp[i]);return inputStream.Dequeue();}}public string next { get { return _stream.ReadLine(); }}public int nextint { get { return int.Parse(Read); }}public long nextlong { get { return long.Parse(Read); }}public double nextdouble { get { return double.Parse(Read); }}public string[] strarray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}public int[] intarray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = nextint; return ret;}public long[] longarray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = nextlong; return ret;}public int[,] intarray2(long h,long w){var ret=new int[h,w];for(long i=0;i<h;++i) {int[] tmparray=intarray(w);for(long j=0;j<w;++j) ret[i,j]=tmparray[j];}return ret;}public long[,] longarray2(long h,long w){var ret=new long[h,w];for(long i=0;i<h;++i) {long[] tmparray=longarray(w);for(long j=0;j<w;++j) ret[i,j]=tmparray[j];}return ret;}public char[] chararray(long N){var ret=new char[N]; string tmp=next;for(int i=0;i<N;++i) ret[i]=tmp[i]; return ret;}public char[,] chararray2(long h,long w){var ret=new char[h,w];for(int i=0;i<h;++i){char[] tmparray=chararray(w);for(int j=0;j<w;++j) ret[i,j]=tmparray[j];}return ret;}public void array2(long[] A,long[] B){int n=A.Length; for(int i=0;i<n;++i){A[i]=nextlong;B[i]=nextlong;}}public void array2(int[] A, int[] B){int n=A.Length; for(int i=0;i<n;++i){A[i]=nextint;B[i]=nextint;}}public void array3(long[] A,long[] B,long[] C){int n=A.Length; for(int i=0;i<n;++i){A[i]=nextlong;B[i]=nextlong;C[i]=nextlong;}}public void array3(int[] A,int[] B,int[] C){int n=A.Length; for(int i=0;i<n;++i){A[i]=nextint;B[i]=nextint;C[i]=nextint;}}}}