#1162970 (C++17) No.3531 Erase Pair

• 問題: No.3531 Erase Pair
• ユーザー: 👑 potato167
• 提出日時: 2026-05-04 23:06:37
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 13 ms / 500 ms
• コード長: 4,669 bytes
• コンパイル時間: 1,863 ms
• コンパイル使用メモリ: 220,532 KB
• 実行使用メモリ: 7,976 KB
• 最終ジャッジ日時: 2026-05-04 23:06:45
• 合計ジャッジ時間: 4,863 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

ファイルパターン	結果
sample	AC * 1
other	AC * 50

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll ILL=2167167167167167167;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using pq_ = priority_queue<T, vector<T>, greater<T>>;
template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
template<class T> void vec_out(vector<T> &p,int ty=0){
    if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
    else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(int)(a&1),a>>=1;}return res;}
template<class T> T square(T a){return a * a;}



void solve();
// DEAR MYSTERIES / TOMOO
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    rep(i, 0, t) solve();
}

void solve(){
    int N;
    cin >> N;
    int Z = 0;
    vector<int> A, B;
    rep(i, 0, N) {
        int a;
        cin >> a;
        if (a > 0) A.push_back(a);
        else if (a < 0) B.push_back(-a);
        else Z++;
    }
    if (Z >= 2) {
        cout << "No\n";
        return;
    }
    if (Z == 0) {
        cout << "Yes\n";
        return;
    }
    if (N % 2 == 0) {
        cout << "No\n";
        return;
    }
    if ((int)A.size() % 2 == 0) {
        cout << "Yes\n";
        return;
    }
    So(A), So(B);
    if (A[0] != B[0]) {
        cout << "Yes\n";
        return;
    }
    rep(rp, 0, 2) {
        swap(A, B);
        int sz = A.size();
        int tmp = 0;
        for (auto x : A) if (x == A[0]) tmp++;
        if (tmp * 2 < sz) {
            cout << "Yes\n";
            return;
        }
        rep(i, 1, A.size()) {
            if (A[i] - A[i - 1] != 0 && A[i] - A[i - 1] != A[0]) {
                cout << "Yes\n";
                return;
            }
        }
        if (3 < A.back() / A[0]) {
            cout << "Yes\n";
            return;
        }
        if (3 == A.back() / A[0]) {
            vector<int> C(4);
            for (auto x : A) C[x / A[0]]++;
            if (C[2] % 2 == 0 || C[3] > 1) {
                cout << "Yes\n";
                return;
            }
        }
    }
    cout << "No\n";
    return;
}

/*
 * 0 は消すことができない
 * 0 が二つ以上あったらそれは無理
 * 0 が一つもないとき、
 * 正負に分けて、絶対値が大きい符号が同じやつを選ぶつづければ別にいける
 * 0 が 1 つだけあるとき
 * N が偶数ならダメ
 * 正の数、負の数がどちらも偶数個なら ok
 * そうでないとき、上記の方法で消していくと
 * 正の数、負の数が 1 つづつ余ることになる
 *
 * これらの和が 0 でなければ同様のことでできる
 *
 * 0 だとしても、どちらかを適当にずらせるのではないか？
 *
 * 例えば 0, 1, 1, 2, -1, -1, -2 の場合
 * これが不可能か
 * どう足掻いても 0, 1, -1 とかになる
 * 正の数 2k + 1 個のうち、小さい方から見て k + 1 個の中に
 * 異なるのが存在すれば ok
 *
 * 隣接差分が A[0], 0 のどちらでもないものが存在したら ok
 * そういうもの同士でペアにできるため
 *
 * そういうものをなくす活動をしないといけない
 * ある箇所を a を穴にしたい
 * a + 1 を 1 個以上残した状態で、
 * 他の a 以上を消せればいい
 * a の数が s 個
 * a より大きい数が t 個だとする。
 * s + t が奇数なら easy ok
 * s + t が偶数かつ、a + 1 が 1 個しかない場合
 * a > 2 なら別に
 * a = 2 のときはどうだろう？
 * C[2] % 2 == 1 かつ、C[3] == 1 であるとき
 * まあ不可能かな
 *
 */