結果
問題 | No.3018 目隠し宝探し |
ユーザー | lif4635 |
提出日時 | 2025-01-25 13:14:25 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 8,163 bytes |
コンパイル時間 | 917 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 101,608 KB |
平均クエリ数 | 1.95 |
最終ジャッジ日時 | 2025-01-25 22:39:21 |
合計ジャッジ時間 | 5,859 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge8 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 1 |
other | AC * 6 RE * 10 WA * 5 |
ソースコード
# inputimport sys# input = sys.stdin.readlineII = lambda : int(input())MI = lambda : map(int, input().split())LI = lambda : list(map(int, input().split()))SI = lambda : input().rstrip()LLI = lambda n : [list(map(int, input().split())) for _ in range(n)]LSI = lambda n : [input().rstrip() for _ in range(n)]MI_1 = lambda : map(lambda x:int(x)-1, input().split())LI_1 = lambda : list(map(lambda x:int(x)-1, input().split()))def graph(n:int, m:int, dir:bool=False, index:int=-1):edge = [set() for i in range(n+1+index)]for _ in range(m):a,b = map(int, input().split())a += indexb += indexedge[a].add(b)if not dir:edge[b].add(a)return edgedef graph_w(n:int, m:int, dir:bool=False, index:int=-1):edge = [set() for i in range(n+1+index)]for _ in range(m):a,b,c = map(int, input().split())a += indexb += indexedge[a].add((b,c))if not dir:edge[b].add((a,c))return edgemod, inf = 998244353, 1001001001001001001ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97yes = lambda : print("Yes")no = lambda : print("No")yn = lambda flag : print("Yes" if flag else "No")def acc(a:list[int]):sa = [0]*(len(a)+1)for i in range(len(a)):sa[i+1] = a[i] + sa[i]return saprinf = lambda ans : print(ans if ans < 1000001001001001001 else -1)alplow = "abcdefghijklmnopqrstuvwxyz"alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)}DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]]DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]]prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]# sys.setrecursionlimit(10**5)# sys.set_int_max_str_digits(0)# https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.pyimport mathfrom bisect import bisect_left, bisect_rightfrom typing import Generic, Iterable, Iterator, TypeVarT = TypeVar('T')class SortedSet(Generic[T]):BUCKET_RATIO = 16SPLIT_RATIO = 24def __init__(self, a: Iterable[T] = []) -> None:"Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)"a = list(a)n = len(a)if any(a[i] > a[i + 1] for i in range(n - 1)):a.sort()if any(a[i] >= a[i + 1] for i in range(n - 1)):a, b = [], afor x in b:if not a or a[-1] != x:a.append(x)n = self.size = len(a)num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)]def __iter__(self) -> Iterator[T]:for i in self.a:for j in i: yield jdef __reversed__(self) -> Iterator[T]:for i in reversed(self.a):for j in reversed(i): yield jdef __eq__(self, other) -> bool:return list(self) == list(other)def __len__(self) -> int:return self.sizedef __repr__(self) -> str:return "SortedSet" + str(self.a)def __str__(self) -> str:s = str(list(self))return "{" + s[1 : len(s) - 1] + "}"def _position(self, x: T) -> tuple[list[T], int, int]:"return the bucket, index of the bucket and position in which x should be. self must not be empty."for i, a in enumerate(self.a):if x <= a[-1]: breakreturn (a, i, bisect_left(a, x))def __contains__(self, x: T) -> bool:if self.size == 0: return Falsea, _, i = self._position(x)return i != len(a) and a[i] == xdef add(self, x: T) -> bool:"Add an element and return True if added. / O(√N)"if self.size == 0:self.a = [[x]]self.size = 1return Truea, b, i = self._position(x)if i != len(a) and a[i] == x: return Falsea.insert(i, x)self.size += 1if len(a) > len(self.a) * self.SPLIT_RATIO:mid = len(a) >> 1self.a[b:b+1] = [a[:mid], a[mid:]]return Truedef _pop(self, a: list[T], b: int, i: int) -> T:ans = a.pop(i)self.size -= 1if not a: del self.a[b]return ansdef discard(self, x: T) -> bool:"Remove an element and return True if removed. / O(√N)"if self.size == 0: return Falsea, b, i = self._position(x)if i == len(a) or a[i] != x: return Falseself._pop(a, b, i)return Truedef lt(self, x: T) -> T | None:"Find the largest element < x, or None if it doesn't exist."for a in reversed(self.a):if a[0] < x:return a[bisect_left(a, x) - 1]def le(self, x: T) -> T | None:"Find the largest element <= x, or None if it doesn't exist."for a in reversed(self.a):if a[0] <= x:return a[bisect_right(a, x) - 1]def gt(self, x: T) -> T | None:"Find the smallest element > x, or None if it doesn't exist."for a in self.a:if a[-1] > x:return a[bisect_right(a, x)]def ge(self, x: T) -> T | None:"Find the smallest element >= x, or None if it doesn't exist."for a in self.a:if a[-1] >= x:return a[bisect_left(a, x)]def __getitem__(self, i: int) -> T:"Return the i-th element."if i < 0:for a in reversed(self.a):i += len(a)if i >= 0: return a[i]else:for a in self.a:if i < len(a): return a[i]i -= len(a)raise IndexErrordef pop(self, i: int = -1) -> T:"Pop and return the i-th element."if i < 0:for b, a in enumerate(reversed(self.a)):i += len(a)if i >= 0: return self._pop(a, ~b, i)else:for b, a in enumerate(self.a):if i < len(a): return self._pop(a, b, i)i -= len(a)raise IndexErrordef index(self, x: T) -> int:"Count the number of elements < x."ans = 0for a in self.a:if a[-1] >= x:return ans + bisect_left(a, x)ans += len(a)return ansdef index_right(self, x: T) -> int:"Count the number of elements <= x."ans = 0for a in self.a:if a[-1] > x:return ans + bisect_right(a, x)ans += len(a)return ansfrom math import isqrth,w = MI()#一回if h == 1 and w == 1:print("!",1,1)exit()# 質問1かいif h == 1:print("?",1,1)res = II()print("!",1,1+isqrt(res))exit()if w == 1:print("?",1,1)res = II()print("!",1+isqrt(res),1)exit()if h == 2:print("?",1,1)res1 = II()print("?",2,1)res2 = II()if res1 == 0:print("!",1,1)if res2 == 0:print("!",2,1)if isqrt(res1)**2 == res1:print("!",1,1+isqrt(res1))if isqrt(res2)**2 == res2:print("!",2,1+isqrt(res2))exit()if w == 2:print("?",1,1)res1 = II()print("?",1,2)res2 = II()if res1 == 0:print("!",1,1)if res2 == 0:print("!",1,2)if isqrt(res1)**2 == res1:print("!",1+isqrt(res1),1)if isqrt(res2)**2 == res2:print("!",1+isqrt(res2),2)exit()print("?",1,1)res1 = II()print("?",h,2)res2 = II()d = [[0]*h for i in range(w)]d2 = [[0]*h for i in range(w)]for i in range(h):for j in range(w):d[i][j] = i**2 + j**2d2[i][j] = (i-h-1)**2 + (j-1)**2# print(d[i])# print(d2[i])for i in range(h):for j in range(h):if d[i][j] == res1 and d2[i][j] == res2:pritn("!",i+1,j+1)exit()