#1038693 (C++23) No.3018 目隠し宝探し

提出ソース
結果

問題	No.3018 目隠し宝探し
コンテスト
ユーザー	kaliafluorido
提出日時	2025-01-25 15:14:09
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	77 ms / 2,000 ms
コード長	10,933 bytes
コンパイル時間	6,015 ms
コンパイル使用メモリ	364,700 KB
実行使用メモリ	25,856 KB
平均クエリ数	2.68
最終ジャッジ日時	2025-01-25 23:42:18
合計ジャッジ時間	8,757 ms
ジャッジサーバーID （参考情報）	judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 21
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma region header
#ifdef LOCAL_ENV

#include <header_all.hpp>

#else

#undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

#include <bits/stdc++.h>
#include <atcoder/all>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>

#define dump(...)
#define CPP_DUMP_SET_OPTION(...)
#define CPP_DUMP_SET_OPTION_GLOBAL(...)
#define CPP_DUMP_DEFINE_EXPORT_OBJECT(...)
#define CPP_DUMP_DEFINE_EXPORT_ENUM(...)
#define CPP_DUMP_DEFINE_EXPORT_OBJECT_GENERIC(...)

#endif

using namespace std;
using namespace atcoder;
using namespace __gnu_pbds;

#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define FOR(i, start, end) for (int i = start; i < (int)(end); ++i)
#define RFOR(i, rstart, rend) for (int i = rstart; i >= (int)(rend); --i)
#define REP(i, end) FOR(i, 0, end)
#define BIT(x, i) (((x)>>(i))&1)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
template<typename T> void read(T& val) {cin >> val;}
template<typename T, typename... Args> void read(T& val, Args&... args) {cin >> val;read(args...);}
#define DEF(type, ...) type __VA_ARGS__;read(__VA_ARGS__)
constexpr ll LINF = 1LL << 60;
constexpr int INF = 1 << 30;
template <typename T> using TREE = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> using Graph = vector<vector<T>>;
template <typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
void yes(bool expr) {cout << (expr ? "Yes" : "No") << "\n";}
template<typename T> bool chmax(T &a, const T &b) { if (a<b){a=b; return true;} else{return false;}}
template<typename T> bool chmin(T &a, const T &b) { if (b<a){a=b; return true;} else{return false;}}
template<typename T> istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T> ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"\n");}return os;}

// 区間をsetで管理する
template<typename T>
struct RangeSet{
	set<pair<T,T>> st;
	T TINF;
	RangeSet(){
		TINF = numeric_limits<T>::max()/2;
		st.emplace(-TINF,-TINF);
		st.emplace(TINF,TINF);
	}
	RangeSet(T tinf):TINF(tinf){
		st.emplace(-TINF,-TINF);
		st.emplace(TINF,TINF);
	}
	// [l,r) covered?
	bool covered(T l, T r){
		auto it = prev(st.lower_bound({l+1,l+1}));
		return it->first <= l && r <= it->second;
	}
	bool covered(T x){
		return covered(x,x+1);
	}
	// [l, r)がカバーされているなら，その区間を返す. されていないなら{TINF,TINF}を返す
	pair<T,T> get_covered(T l, T r){
		auto it = prev(st.lower_bound({l+1,l+1}));
		if(it->first <= l && r <= it->second) return *it;
		return {TINF,TINF};
	}
	pair<T,T> get_covered(T x){
		return get_covered(x,x+1);
	}
	// insert[l,r), 増加量を返す
	T insert(T l, T r){
		auto it = prev(st.lower_bound({l+1,l+1}));
		T ret = 0;
		if(it->first <= l && r <= it->second) return 0;
		if(it->first <= l && l <= it->second){
			l = it->first;
			ret -= it->second - it->first;
			it = st.erase(it);
		}else {
			it = next(it);
		}

		while(it->first <= r){
			ret -= it->second - it->first;
			r = max(r,it->second);
			it = st.erase(it);
		}
		st.emplace(l,r);
		ret += r - l;
		return ret;
	}
	T insert(T x){
		return insert(x,x+1);
	}
	// erase[l,r), 減少量を返す
	T erase(T l, T r){
		auto it = prev(st.lower_bound({l+1,l+1}));
		T ret = 0;
		if(it->first <= l && r <= it->second){
			ret += r - l;
			if(it->first < l) st.emplace(it->first,l);
			if(r < it->second) st.emplace(r,it->second);
			st.erase(it);
			return ret;
		}
		if(it->first <= l && l < it->second){
			ret += it->second - l;
			if(it->first < l) st.emplace(it->first,l);
			it = st.erase(it);
		}else {
			it = next(it);
		}

		while(it->first < r){
			ret += it->second - it->first;
			if(r < it->second) {
				ret -= it->second - r;
				st.emplace(r,it->second);
			}
			it = st.erase(it);
		}
		return ret;
	}
	T erase(T x){
		return erase(x,x+1);
	}
	// number of ranges
	int size(){
		return st.size()-2;
	}
	T mex(T x = 0){
		auto it = prev(st.lower_bound({x+1,x+1}));
		if(it->first <= x && x < it->second ) return it->second;
		return x;
	}
	void output(){
        cout<<"RangeSet : ";
        for(auto &p:st){
            if(p.first==-TINF || p.second==TINF) continue;
            cout<<"["<<p.first<<", "<<p.second<<") ";
        }
        cout << endl;
    }
};

template<class T>
struct Binomial{
	std::vector<T> fact_vec, fact_inv_vec;
	void extend(int m = -1){
        int n = fact_vec.size();
        if (m == -1) m = n * 2;
        if (n >= m) return;
        fact_vec.resize(m);
        fact_inv_vec.resize(m);
        for (int i = n; i < m; i++){
            fact_vec[i] = fact_vec[i - 1] * T(i);
        }
        fact_inv_vec[m - 1] = T(1) / fact_vec[m - 1];
        for (int i = m - 1; i > n; i--){
            fact_inv_vec[i - 1] = fact_inv_vec[i] * T(i);
        }
    }
    Binomial(int MAX = 2){
        fact_vec.resize(1, T(1));
        fact_inv_vec.resize(1, T(1));
        extend(MAX + 1);
    }

    T fact(int i){
        if (i < 0) return 0;
        while (int(fact_vec.size()) <= i) extend();
        return fact_vec[i];
    }
    T invfact(int i){
        if (i < 0) return 0;
        while (int(fact_inv_vec.size()) <= i) extend();
        return fact_inv_vec[i];
    }
    T C(int a, int b){
        if (a < b || b < 0) return 0;
        return fact(a) * invfact(b) * invfact(a - b);
    }
    T invC(int a, int b){
        if (a < b || b < 0) return 0;
        return fact(b) * fact(a - b) *invfact(a);
    }
    T P(int a, int b){
        if (a < b || b < 0) return 0;
        return fact(a) * invfact(a - b);
    }
    T inv(int a){
        if (a < 0) return inv(-a) * T(-1);
        if (a == 0) return 1;
        return fact(a - 1) * invfact(a);
    }
};

// 有向グラフをDAGに変換する
Graph<int> toDAG(const Graph<int> &G){
	int n = G.size();
	scc_graph scc(n);
	REP(i,n) for(auto &to:G[i]) scc.add_edge(i,to);
	auto sccs = scc.scc();
	int m = sccs.size();
	vector<int> id(n);
	REP(i,m) for(auto &v:sccs[i]) id[v] = i;
	Graph<int> ret(m);
	REP(i,n) for(auto &to:G[i]) if(id[i]!=id[to]) ret[id[i]].push_back(id[to]);
	REP(i,m) sort(ALL(ret[i])), ret[i].erase(unique(ALL(ret[i])),ret[i].end());
	return ret;
}

/* 文字列、数列が一様か判定 */
template <typename T> struct UniformSegmentChecker {
	const T &v; const int n; vector<int> diff;
	UniformSegmentChecker(const T &v) : v(v), n(v.size()), diff(v.size(),0) { REP(i,n-1){ diff[i+1] = diff[i] + (v[i] != v[i+1]);} }
	bool is_uniform(int l, int r) const { assert(0 <= l && l < r && r <= n); return diff[l] == diff[r-1]; }
};
/* 回文判定 */ bool isPalindrome(const string &s){int sz=s.size(); REP(i,sz/2){if(s[i]!=s[sz-1-i])return false;} return true;}
/* 座標圧縮 */ template<typename T> vector<int> compress(const vector<T>&A){vector<int> ret(A.size()); auto tmp = A; sort(ALL(tmp)); tmp.erase(unique(ALL(tmp)), tmp.end()); REP(i,A.size()) ret[i] = lower_bound(ALL(tmp), A[i]) - tmp.begin(); return ret;}
/* 約数列挙　整数nの約数のvectorを返す */ vector<ll> enumdiv(ll n){vector<ll>s; for(ll i = 1;i*i<=n;i++){if(n%i==0){s.push_back(i);if(i*i!=n)s.push_back(n/i);}}return s;}
/* 素因数分解 pair<素数、指数>のvectorを返す */ vector<pli> primeDecomposition(ll x){vector<pli> ret;int i=2,sq=99,d=2;while(i<=sq){int k=0;while(x%i==0){x/=i;++k;}if(k>0){ret.emplace_back(i,k);}if(k>0 || i==97) {sq = sqrt(x)+0.5;}if(i<4){i = (i<<1)-1;}else{i += d;d ^= 6;}}if(x>1) ret.emplace_back(x,1);return ret;}
/* エラトステネスの篩　n未満の素数を列挙。isprimeには素数かどうかが入っている */ vector<bool> isprime;vector<int> era(int n) {isprime.resize(n, true);vector<int> res;isprime[0] = false; isprime[1] = false;for (int i = 2; i < n; ++i){if (isprime[i]) {res.push_back(i);for (int j = i*2; j < n; j += i) isprime[j] = false;}}return res;}
/* トポロジカルソート */ vector<int> topo_sort(const Graph<int> &G){int n = G.size();vector<int> deg(n), ret;for(const auto &v:G)for(const auto &to:v) ++deg[to];queue<int> que;REP(i,n) if(deg[i]==0)que.push(i);while(!que.empty()){const int from = que.front();que.pop();ret.push_back(from);for(const auto &to:G[from])if(--deg[to]==0) que.push(to);}return ret;};
/* 拡張ユークリッドの互除法 [gcd,x,y] ax+by=gcd(a,b) */ tuple<ll,ll,ll> ex_gcd(ll a, ll b){if(b==0) return {a,1,0}; auto [g,x,y] = ex_gcd(b, a%b); return {g,y,x-a/b*y};}
/* 辞書順で次の分割数を求める */ template<typename T> bool next_partition(vector<T> &a){const int n = a.size(); if(n<=1) {return false;} T sum=a[n-1]; a.pop_back(); while(true){T x = a.back(); a.pop_back(); sum += x; if(a.empty() || a.back() > x){a.push_back(x+1); a.resize(a.size()+sum-x-1, 1); break;}} return true;}
/* iを中心として回文となる半径を全て求める O(n) */ template <typename T> vector<int> manachar(const T &s) {int n = s.size();vector<int>r(n);int i=0,j=0;while(i<n){while(i-j>=0&&i+j<n&&s[i-j]==s[i+j]){++j;}r[i]=j;int k=1;while(k<j&&k+r[i-k]<j) {r[i+k]=r[i-k],++k;}i+=k;j-=k;}return r;}
/* 切り上げ割り算。ans以上の最小の整数を返す ceil_div(10,3) = 4, ceil_div(10,-3) = -3 */ ll ceil_div(ll a, ll b) { return a/b + (a%b && (a^b)>=0); }

using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;
istream &operator>>(istream&is,mint&p){ll x;cin >> x;p=x; return is;}
ostream &operator<<(ostream&os,const mint&p){os << p.val();return os;}

#pragma endregion header

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int h,w;
	cin >> h >> w;
	if(h==1 && w==1){
		cout << "! 1 1" << endl;
		return 0;
	}
	if(h==1){
		cout << "? 1 1" << endl;
		int ret;
		cin >> ret;
		FOR(j,1,w+1){
			int d = j-1;
			if(ret == d*d){
				cout << "! 1 " << j << endl;
				return 0;
			}
		}
	}
	if(w==1){
		cout << "? 1 1" << endl;
		int ret;
		cin >> ret;
		FOR(i,1,h+1){
			int d = i-1;
			if(ret == d*d){
				cout << "! " << i << " 1" << endl;
				return 0;
			}
		}
	}

	cout << "? 1 1" << endl;
	int d1;
	cin >> d1;
	cout << "? 1 " << w << endl;
	int d2;
	cin >> d2;
	FOR(i,1,h+1)FOR(j,1,w+1){
		int di1 = i-1;
		int dj1 = j-1;
		int di2 = i-1;
		int dj2 = w-j;
		if(di1*di1+dj1*dj1 == d1 && di2*di2+dj2*dj2 == d2){
			cout << "! " << i << " " << j << endl;
			return 0;
		}
	}


	return 0;
}
yukicoder

結果

ソースコード
