結果
| 問題 | 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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 98 ms
40,256 KB |
| testcase_01 | AC | 89 ms
40,976 KB |
| testcase_02 | AC | 87 ms
40,264 KB |
| testcase_03 | AC | 88 ms
40,516 KB |
| testcase_04 | AC | 89 ms
40,764 KB |
| testcase_05 | AC | 88 ms
40,708 KB |
| testcase_06 | AC | 86 ms
40,980 KB |
| testcase_07 | AC | 88 ms
42,632 KB |
| testcase_08 | AC | 89 ms
41,072 KB |
| testcase_09 | AC | 88 ms
38,420 KB |
| testcase_10 | AC | 87 ms
42,516 KB |
| testcase_11 | AC | 90 ms
40,268 KB |
| testcase_12 | AC | 87 ms
40,520 KB |
| testcase_13 | AC | 97 ms
42,772 KB |
| testcase_14 | AC | 110 ms
38,924 KB |
| testcase_15 | AC | 92 ms
40,452 KB |
| testcase_16 | AC | 91 ms
40,724 KB |
| testcase_17 | AC | 93 ms
42,556 KB |
| testcase_18 | AC | 90 ms
40,772 KB |
| testcase_19 | AC | 92 ms
42,684 KB |
| testcase_20 | AC | 90 ms
42,512 KB |
| testcase_21 | AC | 89 ms
42,632 KB |
| testcase_22 | AC | 90 ms
42,640 KB |
| testcase_23 | AC | 88 ms
40,732 KB |
| testcase_24 | AC | 88 ms
42,268 KB |
| testcase_25 | AC | 90 ms
40,648 KB |
| testcase_26 | AC | 93 ms
38,796 KB |
| testcase_27 | AC | 94 ms
38,288 KB |
| testcase_28 | AC | 86 ms
43,072 KB |
| testcase_29 | AC | 87 ms
40,900 KB |
コンパイルメッセージ
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;
else
high = 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;
else
high = 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;}
}
}
}