結果
| 問題 | No.3596 Queen Score Attack 1 |
| コンテスト | |
| ユーザー |
 Salaadaaa
|
| 提出日時 | 2026-07-24 22:16:34 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.90.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 16,297 bytes |
| 記録 | |
| コンパイル時間 | 3,880 ms |
| コンパイル使用メモリ | 385,280 KB |
| 実行使用メモリ | 5,888 KB |
| 最終ジャッジ日時 | 2026-07-24 22:19:21 |
| 合計ジャッジ時間 | 6,202 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 30 WA * 1 |
ソースコード
#ifdef LOCAL
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
/*
#include <atcoder/all>
#define ACL_included
*/
# pragma GCC optimize("O3,unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using gll = greater<ll>;
template <typename T>
using vec = vector<T>;
template <typename T>
using vvec = vector<vector<T>>;
template <typename T>
using uset = unordered_set<T>;
template <typename T, typename U>
using umap = unordered_map<T, U>;
template <typename T>
using pque = priority_queue<T>;
template <typename T>
using rpque = priority_queue<T,vec<T>,greater<T>>;
template <typename T>
using deq = deque<T>;
using vll = vec<ll>;
using vbool = vec<bool>;
using vstr = vec<string>;
using vchar = vec<char>;
using vvll = vvec<ll>;
using vvbool = vvec<bool>;
using vvstr = vvec<string>;
using vvchar = vvec<char>;
template <typename T, typename U>
using vpair = vec<pair<T, U>>;
using pll = pair<ll,ll>;
using usll = uset<ll>;
using umll = umap<ll,ll>;
using dqll = deq<ll>;
using pqll = pque<ll>;
using rpqll = rpque<ll>;
using qll = queue<ll>;
using vpll = vpair<ll,ll>;
#ifdef ACL_included
using namespace atcoder;
using mint = modint;
using vmint = vec<mint>;
using vvmint = vvec<mint>;
#endif
#define segt segtree
#define fwt fenwick_tree
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
#define repab(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);i++)
#define rrep(i,a,b) for(ll i=(ll)(a);i>=(ll)(b);i--)
#define repv(e,v) for(auto& e: v)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YorN(x) if(x){Yes;}else{No;}
const ll INF = 1ll<<62;
const vll DX = {1,0,-1,0,1,-1,-1,1};
const vll DY = {0,1,0,-1,1,1,-1,-1};
const char spc = ' ';
template<typename T> size_t HashCombine(const size_t seed,const T &v){
return seed^(std::hash<T>()(v)+0x9e3779b9+(seed<<6)+(seed>>2));
}
template<typename T, typename S> struct std::hash<std::pair<T,S>>{
size_t operator()(const std::pair<T,S> &keyval) const noexcept {
return HashCombine(std::hash<T>()(keyval.first), keyval.second);
}
};
template <typename T>
bool chmax(T& a, const T& b){
if(a < b){ a = b; return true; }
return false;
}
template <typename T>
bool chmin(T& a, const T& b){
if(a > b){ a = b; return true; }
return false;
}
template <typename T>
inline istream& operator>>(istream& is, vec<T>& v) {
rep(i, v.size()) is >> v[i];
return is;
}
template <typename T>
inline istream& operator>>(istream& is, vvec<T>& v) {
rep(i, v.size()) is >> v[i];
return is;
}
template <typename T>
inline ostream& operator<<(ostream& os, vec<T>& v) {
rep(i, v.size()) os << v[i] << (i+1==v.size() ? "" : " ");
return os;
}
template <typename T>
inline ostream& operator<<(ostream& os, vvec<T>& v) {
rep(i, v.size()){
os << v[i];
if(i+1 != v.size()) os << endl;
}
return os;
}
struct Edge{
ll from;
ll to;
ll w;
Edge(ll from, ll to, ll w) : from(from), to(to), w(w) {}
bool operator>(Edge* other) const {
return this->w > other->w;
}
bool operator<(Edge* other) const {
return other > this;
}
};
class UnionFind {
private:
vll par;
vll siz;
vll rnk;
public:
UnionFind(ll n) {
par.resize(n, -1);
siz.resize(n, 1);
rnk.resize(n, 0);
}
ll root(ll x) {
if (par[x] == -1) {
return x;
} else {
return par[x] = root(par[x]);
}
}
bool issame(ll x, ll y) {
return root(x) == root(y);
}
ll size(ll x) {
return siz[root(x)];
}
void unite(ll x, ll y) {
ll rx = root(x);
ll ry = root(y);
if (rx != ry) {
if (rnk[rx] < rnk[ry]) {
swap(rx, ry);
}
par[ry] = rx;
siz[rx] += siz[ry];
if (rnk[rx] == rnk[ry]) {
rnk[rx]++;
}
}
}
};
using Graph = vec<vec<Edge>>;
void G_in(vvll& G, const ll m){
rep(i,m){
ll u, v;
cin >> u >> v;
u--; v--;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
}
void G_in1(vvll& G, const ll m){
rep(i,m){
ll u, v;
cin >> u >> v;
u--; v--;
G[u].emplace_back(v);
}
}
void w_G_in(Graph& G, const ll m){
rep(i,m){
ll u, v, w;
cin >> u >> v >> w;
u--; v--;
G[u].emplace_back(Edge{u, v, w});
G[v].emplace_back(Edge{v, u, w});
}
}
void w_G_in1(Graph& G, const ll m){
rep(i,m){
ll u, v, w;
cin >> u >> v >> w;
u--; v--;
G[u].emplace_back(Edge{u, v, w});
}
}
void dfs(const ll u, const vvll& G, vbool& visited){
visited[u] = true;
repv(v, G[u]){
if(!visited[v]){
dfs(v, G, visited);
}
}
visited[u] = false;
return;
}
void bfs(const vvll& G, const ll start){
vbool visited(G.size(), false);
qll Q;
Q.push(start);
visited[start] = true;
while(!Q.empty()){
ll u = Q.front();
Q.pop();
repv(v, G[u]){
if(!visited[v]){
visited[v] = true;
Q.push(v);
}
}
}
}
ll binarySearch(ll ng, ll ok, function<bool(ll)> isOK){
while(abs(ok-ng) > 1){
ll mid = (ok+ng)/2;
if(isOK(mid)){
ok = mid;
}
else{
ng = mid;
}
}
return ok;
}
vll bellman_ford(const Graph& G, const ll n, const ll start, bool& negative_cycle){
negative_cycle = false;
vll D(n, INF);
D[start] = 0;
rep(i,n){
bool update = false;
rep(v,n){
if(D[v] == INF) continue;
repv(e, G[v]){
if(D[e.to] > D[v] + e.w){
update = true;
D[e.to] = D[v] + e.w;
}
}
}
if(!update) return D;
if(i == n-1 && update) negative_cycle = true;
}
return D;
}
vll dijkstra_dense(const Graph& G, const ll n, const ll start){
vbool used(n, false);
vll D(n, INF);
D[start] = 0;
rep(_,n){
ll min_d = INF;
ll min_v = -1;
rep(v,n){
if(!used[v] && D[v] < min_d){
min_d = D[v];
min_v = v;
}
}
if(min_v == -1) return D;
repv(e, G[min_v]){
D[e.to] = min(D[e.to], D[min_v] + e.w);
}
used[min_v] = true;
}
return D;
}
vll dijkstra(const Graph& G, const ll n, const ll start){
vll D(n, INF);
D[start] = 0;
rpque<pll> Q;
Q.push({D[start], start});
while(!Q.empty()){
ll v = Q.top().second;
ll d = Q.top().first;
Q.pop();
if(d > D[v]) continue;
repv(e, G[v]){
if(D[e.to] > D[v] + e.w){
D[e.to] = D[v] + e.w;
Q.push({D[e.to], e.to});
}
}
}
return D;
}
vvll Warshall_Floyd(const Graph& G, const ll n, bool& negative_cycle){
vvll Dp(n, vll(n, INF));
rep(v,n){
Dp[v][v] = 0;
repv(e, G[v]){
Dp[v][e.to] = e.w;
}
}
rep(k,n){
rep(i,n){
rep(j,n){
Dp[i][j] = min(Dp[i][j], Dp[i][k] + Dp[k][j]);
}
}
}
negative_cycle = false;
rep(v,n){
if(Dp[v][v] < 0){
negative_cycle = true;
break;
}
}
return Dp;
}
Graph Kruskal(const Graph& G){
rpque<pair<ll,pll>> Q;
const ll n = G.size();
rep(i,n){
rep(j,G[i].size()){
Q.push({G[i][j].w,{i,j}});
}
}
UnionFind uf(n);
Graph F(n);
while(!Q.empty()){
ll w; pll idx;
tie(w,idx) = Q.top();
Q.pop();
ll i,j; tie(i,j) = idx;
const Edge e = G[i][j];
const ll u = e.from, v = e.to;
if(!uf.issame(u, v)){
F[u].emplace_back(e);
uf.unite(u, v);
}
}
return F;
}
bool is_prime(ll n){
if(n % 2 == 0) return false;
if(n % 3 == 0) return false;
for(ll i = 1; (6*i-1)*(6*i-1) <= n; i++){
ll k = 6*i-1;
if(n % k == 0){
return false;
}
k = 6*i+1;
if(n % k == 0){
return false;
}
}
return true;
}
vpll factor(ll n){
vpll F;
if(n % 2 == 0){
ll cnt = 0;
while(!(n&1)){
cnt++;
n>>=1;
}
if(cnt > 0) F.emplace_back(pll{2, cnt});
}
if(n % 3 == 0){
ll cnt = 0;
while(n % 3 == 0){
cnt++;
n /= 3;
}
if(cnt > 0) F.emplace_back(pll{3, cnt});
}
for(ll i = 1; (6*i-1)*(6*i-1) <= n; i++){
ll k = 6*i-1;
if(n % k == 0){
ll cnt = 0;
while(n % k == 0){
cnt++;
n /= k;
}
F.emplace_back(pll{k, cnt});
}
k = 6*i+1;
if(n % k == 0){
ll cnt = 0;
while(n % k == 0){
cnt++;
n /= k;
}
F.emplace_back(pll{k, cnt});
}
}
if(n != 1) F.emplace_back(pll{n, 1});
return F;
}
vll divisor(ll n){
vll D;
for(ll i = 1; i*i <= n; i++){
if(n % i == 0){
D.emplace_back(i);
if(i != n/i) D.emplace_back(n/i);
}
}
return D;
}
#ifdef ACL_included
mint power(const mint a, const ll b){
mint ans = 1;
mint p = a;
rep(i, 63){
if((b>>i)&1) ans *= p;
p *= p;
}
return ans;
}
const ll facMax = 0;//1e8;
vec<mint> Fac(facMax);
void nCrInit(void){
Fac[0] = Fac[1] = 1;
repab(i,2,facMax-1){
Fac[i] = Fac[i-1] * i;
}
}
mint nCr(ll n, ll r){
if(n < r) return 0;
else return Fac[n] / Fac[r] / Fac[n-r];
}
#endif
template <typename T>
inline vvec<T>& operator*(vvec<T>& V, vvec<T>& W){
vvec<T> R(V.size(), vec<T>(W[0].size()));
rep(i,V.size()){
rep(k,W.size()){
rep(j,W[0].size()){
R[i][j] += V[i][k] * W[k][j];
}
}
}
return R;
}
void solve(void){
ll h,w; cin >> h >> w;
vvll A(h,vll(w)); cin >> A;
rep(i,h){
rep(j,w){
ll a = A[i][j];
rep(k,w){
if(k == j) continue;
if(a + A[i][k] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<endl;
cout << "infinite" << endl;
return;
}
else if(a + A[i][k] == 0){
rep(l,h){
if(l == i) continue;
if(A[l][k] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<l<<endl;
cout << "infinite" << endl;
return;
}
}
repab(l,-min(i,k),min(h-i-1,w-k-1)){
if(l == 0) continue;
if(A[i+l][k+l] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<l<<endl;
cout << "infinite" << endl;
return;
}
}
repab(l,-min(i,w-k-1),min(h-i-1,k)){
if(l == 0) continue;
if(A[i+l][k-l] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<l<<endl;
cout << "infinite" << endl;
return;
}
}
}
}
rep(k,h){
if(k == i) continue;
if(a + A[k][j] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<endl;
cout << "infinite" << endl;
return;
}
else if(a + A[k][j] == 0){
rep(l,w){
if(l == j) continue;
if(A[k][l] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<l<<endl;
cout << "infinite" << endl;
return;
}
}
repab(l,-min(k,j),min(h-k-1,w-j-1)){
if(l == 0) continue;
if(A[k+l][j+l] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<l<<endl;
cout << "infinite" << endl;
return;
}
}
repab(l,-min(k,w-j-1),min(h-k-1,j)){
if(l == 0) continue;
if(A[k+l][j-l] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<l<<endl;
cout << "infinite" << endl;
return;
}
}
}
}
repab(k,-min(i,j),min(h-i-1,w-j-1)){
if(k == 0) continue;
if(a + A[i+k][j+k] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<endl;
cout << "infinite" << endl;
return;
}
else if(a + A[i+k][j+k] == 0){
rep(l,w){
if(l == j+k) continue;
if(A[i+k][l] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<l<<endl;
cout << "infinite" << endl;
return;
}
}
rep(l,h){
if(l == i+k) continue;
if(A[l][j+k] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<l<<endl;
cout << "infinite" << endl;
return;
}
}
repab(l,-min(i+k,w-j-k-1),min(h-i-k-1,j+k)){
if(l == 0) continue;
if(A[i+k+l][j+k-l] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<l<<endl;
cout << "infinite" << endl;
return;
}
}
}
}
repab(k,-min(i,w-j-1),min(h-i-1,j)){
if(k == 0) continue;
if(a + A[i+k][j-k] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<endl;
cout << "infinite" << endl;
return;
}
else if(a + A[i+k][j-k] == 0){
rep(l,w){
if(l == j-k) continue;
if(A[i+k][l] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<l<<endl;
cout << "infinite" << endl;
return;
}
}
rep(l,h){
if(l == i+k) continue;
if(A[l][j-k] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<l<<endl;
cout << "infinite" << endl;
return;
}
}
repab(l,-min(i+k,j-k),min(h-i-k-1,w-j+k-1)){
if(l == 0) continue;
if(A[i+k+l][j-k+l] > 0){
//cout<<i<<spc<<j<<spc<<k<<spc<<l<<endl;
cout << "infinite" << endl;
return;
}
}
}
}
}
}
cout << "finite" << endl;
}
int main(void){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
#ifdef ACL_included
modint::set_mod(998244353);
#endif
ll t; cin >> t;
while(t--) solve();
return 0;
}