提出 #67346958

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200000;

class Solver {
    int n;
    ll v[MAXN], a[MAXN];
    unordered_map<ll,int> cp0, cn0;

    bool mag(ll *b){
        ll g = std::gcd(b[1], b[0]);
        ll p = b[1]/g, q = b[0]/g;
        for(int i=1;i<n;i++){
            unsigned long long L = (unsigned long long)b[i]*q;
            unsigned long long R = (unsigned long long)b[i-1]*p;
            if(L!=R) return false;
        }
        return true;
    }

    bool pat(bool *s,int t){
        for(int i=0;i<n;i++){
            bool w = t<2 ? (t==0) : ((i&1)==(t&1));
            if(s[i]!=w) return false;
        }
        return true;
    }

public:
    bool solve(){
        cin>>n;
        cp0.clear(); cn0.clear();
        for(int i=0;i<n;i++){
            cin>>v[i];
            a[i]=llabs(v[i]);
            if(v[i]>0) cp0[a[i]]++;
            else       cn0[a[i]]++;
        }
        if(n<=2) return true;
        sort(a,a+n);
        ll *b = new ll[n];
        bool *s = new bool[n];
        bool *d = new bool[n];
        bool ok=false;
        for(int dir=0;dir<2;dir++){
            memcpy(b,a,sizeof(ll)*n);
            if(dir) reverse(b,b+n);
            if(!mag(b)) continue;
            auto cp=cp0, cn=cn0;
            for(int i=0;i<n;i++){
                ll x=b[i];
                if(cp[x]>0) s[i]=1, cp[x]--;
                else         s[i]=0, cn[x]--;
            }
            for(int i=0;i<n;i++) d[i]=s[n-1-i];
            for(auto arr:{s,d}){
                for(int t=0;t<4 && !ok;t++)
                    if(pat(arr,t)) ok=true;
                if(ok) break;
            }
            if(ok) break;
        }
        return ok;
    }
};

int main(){
    int T; 
    cin>>T;
    Solver S;
    while(T--){
        cout<<(S.solve()?"Yes\n":"No\n");
    }
    return 0;
}

提出情報

ジャッジ結果