#933029 (C++14) No.2555 Intriguing Triangle

提出ソース
結果

問題	No.2555 Intriguing Triangle
コンテスト
ユーザー	eq_K
提出日時	2023-12-01 11:15:25
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	WA
実行時間	-
コード長	13,676 bytes
コンパイル時間	3,357 ms
コンパイル使用メモリ	216,816 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-09-26 15:33:18
合計ジャッジ時間	4,064 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 22 WA * 6
権限があれば一括ダウンロードができます
ソースコード

raw source code
/*
#define _GLIBCXX_DEBUG
//*/
#include <bits/stdc++.h>
/*
#include <atcoder/all>
using namespace atcoder;
//*/
using namespace std;
#define dbl double
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define tl3 tuple<ll,ll,ll>
#define vi vector<int>
#define vd vector<double>
#define vc vector<char>
#define vl vector<ll>
#define vb vector<bool>
#define vs vector<string>
#define vvi vector<vector<int>>
#define vvd vector<vector<double>>
#define vvc vector<vector<char>>
#define vvb vector<vector<bool>>
#define vvl vector<vector<ll>>
#define vvvi vector<vector<vector<int>>>
#define vvvd vector<vector<vector<double>>>
#define vvvc vector<vector<vector<char>>>
#define vvvl vector<vector<vector<ll>>>
#define vvvvi vector<vector<vector<vector<int>>>>
#define vvvvd vector<vector<vector<vector<double>>>>
#define vvvvc vector<vector<vector<vector<char>>>>
#define vvvvl vector<vector<vector<vector<ll>>>>
#define vpi vector<pii>
#define vpl vector<pll>
#define prq priority_queue
#define prq2 priority_queue<ll,vl, greater<ll>>
#define seti set<int>
#define setl set<ll>
#define quel queue<ll>
#define pb push_back
#define ps push
#define ins insert
#define rev reverse
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define forv(i,V) for(const auto& i:V)
#define rep(i,n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i,j,n) for (ll i = (ll)(j);i < (ll)(n);i++)
#define rep2(i,n) for(ll i=(ll)(n-1);i>=0ll;i--)
#define repi2(i,n,j) for(ll i=(ll)(n-1);i>=(ll)(j);i--)
#define faster ios::sync_with_stdio(false);std::cin.tie(nullptr);
const double PI=3.14159265358979323846;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
vl dxs = {1, 0, -1, 0};
vl dys = {0, 1, 0, -1};
ll max(int a,ll b){return max((ll)a,b);}
ll max(ll a,int b){return max((ll)b,a);}
ll min(int a,ll b){return min((ll)a,b);}
ll min(ll a,int b){return min((ll)b,a);}
ll gcd(ll a,ll b){if(b==0){return a;}else{return gcd(b,a%b);}}
ll lcm(ll a,ll b){return (a/gcd(a,b))*b;}
ll indexlb(vl &v,ll x){auto it=lb(all(v),x);ll index=it-v.begin();return index;}
ll indexub(vl &v,ll x){auto it=ub(all(v),x);ll index=it-v.begin();return index;}
ll setlb(setl &s,ll x){auto it=s.lb(x); return *it;}//番目ではなく要素が返ってくる
ll setub(setl &s,ll x){auto it=s.ub(x); return *it;}//番目ではなく要素が返ってくる
void setpre(double d,ll x){cout<<fixed<<setprecision(x)<<d<<endl;}
void ldsetpre(ld d,ll x){cout<<fixed<<setprecision(x)<<d<<endl;}
template <typename T>
void output(vector<T> &A) {rep(i,A.size()){cout<<A[i];if(i!=A.size()-1){cout<<" ";}else{cout<<endl;}}}
template <typename T>
void cinvec(vector<T> &A){rep(i,A.size()) cin>>A[i];}
template <typename T>
void coutvece(vector<T> &A){for(ll i=0;i<A.size();i++) cout <<A[i]<<endl;}
template <typename T>
bool chmin(T &a,const T &b){if(b<a){a=b; return 1;} return 0;}
template <typename T>
bool chmax(T &a,const T &b){if(b>a){a=b; return 1;} return 0;}
void yesno(bool i){if(i)cout<<"yes"<<endl;else cout<<"no"<<endl;}
void YesNo(bool i){if(i)cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void YESNO(bool i){if(i)cout<<"YES"<<endl;else cout<<"NO"<<endl;}
ll suretu_sum(vl a){//数列の要素の和
    ll n=a.size();
    ll res=0;
    rep(i,n){
        res+=a[i];
    }
    return res;
}
ll maxele(vl a){//aで一番大きい要素
    return *max_element(all(a));
}
ll minele(vl a){//aで一番小さい要素
    return *min_element(all(a));
}
ll modinv(ll a,ll m){//mod m上でのaの逆元
    ll b=m,u=1,v=0;
    while(b){
        ll t=a/b;
        a-=t*b; swap(a,b);
        u-=t*v; swap(u,v);
    }
    u%=m;
    if(u<0) u+=m;
    return u;
}
ll modwari(ll a,ll b,ll m){//mod m上でのa/b
    ll ans=a*modinv(b,m)%m;
    return ans;
}
ll modpow(ll a,ll n,ll mod) {
    ll res=1;
    while(n>0) {
        if(n&1) res=(res*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
vl factt,invv,fact_inv;
void combjyunbi(ll size,ll mod){
    factt.resize(size+5);
    fact_inv.resize(size+5);
    invv.resize(size+5);
    factt[0]=factt[1]=1;
    fact_inv[0]=fact_inv[1]=1;
    invv[1]=1;
    repi(i,2,size+5){
        factt[i]=factt[i-1]*i%mod;
        invv[i]=mod-invv[mod%i]*(mod/i)%mod;
        fact_inv[i]=fact_inv[i-1]*invv[i]%mod;
    }
}
//combjyunbiしてから！！！
ll combmod(ll n,ll k,ll mod){
    return factt[n]*(fact_inv[k]*fact_inv[n-k]%mod)%mod;
}
ll combmod2(ll n,ll k,ll mod){
    ll ans=1;
    repi(i,1,k+1){
        ans*=modwari(n-i+1,i,mod);
        ans%=mod;
    }
    return ans;
}
//nが大きく、kが小さい場合(計算量はO(k))
struct edge {
    ll from;   //辺の始点
    ll to;     //辺の終点
    ll leng;   //辺の重み
};
struct yukoedge{
    ll to;
};
using Graph =vvl;
using Graph2=vector<vector<edge>>;
using Graph3=vector<vector<yukoedge>>;//.pb({x})で作成
vl topo_sort(const Graph3 &G,ll a){//bfs できない場合は返り値のsize≠n a=0ならtoposo a=1なら一意性
    vl ans;
    ll n=G.size();
    vl ind(n);// ind[i]: 頂点iに入る辺の数(次数)
    rep(i,n){//count index
        forv(e,G[i]){
            ind[e.to]++;
        }
    }
    quel que;//辞書順最小が欲しかったらprq2にする
    rep(i,n){//次数が0の点
        if(ind[i]==0){
            que.push(i);
        }
    }
    bool itii=true;
    while(!que.empty()){//bfs
        ll now=que.front();
        if(que.size()!=1) itii=false;
        ans.pb(now);
        que.pop();
        forv(e,G[now]){
            ind[e.to]--;
            if(ind[e.to]==0) {
                que.push(e.to);
            }
        }
    }
    if(a==0) return ans;
    else{
        vl res;
        if(itii) res.pb(1);
        else res.pb(0);
        return res;
    }
}
vl sieve(ll n){
//fast_soinsuの前処理 O(NloglogN)
//vl min_factor=sieve(1e6)などでコピー
//min_factor[n]でnを割り切る最小の素数
    vl min_factor(n+1);
    rep(i,n+1) min_factor[i] = i;
    for(ll i=2;i*i<=n;i++){
        if(min_factor[i]==i){
            for(ll j=2;i*j<= n;j++){
                if(min_factor[i*j]>i){
                    min_factor[i*j]=i;
                }
            }
        }
    }
    return min_factor;
}
vector<pll> fast_factorize(const vl &min_factor,ll n){
//N以下の正整数すべてを素因数分解するときに有効(全体でNlogN,1つにつきlogN)
//vl min_factor=sieve(1e6);で前計算 O(NloglogN)
    vector<pll> res;
    while(n>1){
        ll p=min_factor[n];
        ll ex=0;
        while(min_factor[n]==p){
            n/=p;
            ex++;
        }
        res.pb({p,ex});
    }
    return res;
}
vector<pll> factorize(ll n){//素因数分解{因数,乗数}　O(sqrt(n))
    vector<pll> ans;
    for(ll a=2;a*a<=n;a++){
        if(n%a!=0) continue;
        ll ex=0;
        while(n%a==0){
            ex++;
            n/=a;
        }
        ans.pb({a,ex});
    }
    if(n!=1) ans.push_back({n, 1});
    return ans;
}
vl fast_divisor(vl &min_factor,ll n){
    //n以下の正整数すべてに対して約数を列挙するときに有効(1つにつきO(d(n)))
    //vl min_factor=sieve(1e6); で前計算　O(NloglogN)
    vl res({1});
    auto pf=fast_factorize(min_factor,n);
    forv(p,pf){
        ll s=res.size();
        rep(i,s){
            ll v=1;
            rep(j,p.se){
                v*=p.fi; res.pb(res[i]*v);
            }
        }
    }
    return res;
}
vl divisor(ll n){//約数列挙(sqrt(n))
    vl ret;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            ret.push_back(i);
            if(i*i!=n) ret.push_back(n/i);
        }
    }
    return ret;
}
vb eratos(ll n){//n以下の整数の素数判定(O(NloglogN)) 1-indexed
    vb primedesu(n+1,true);
    primedesu[1]=false;
    repi(p,2,n+1){
        if(!primedesu[p]) continue;
        for(ll q=2*p; q<=n; q+=p){
            primedesu[q]=false;
        }
    }
    return primedesu;
}
bool isprime(ll n){//素数判定 (O(sqrt(n)))
    if(n<2) return false;
    else if(n==2) return true;
    else if(n%2==0) return false;
    ll sqrtn=floor(sqrt(n));
    for(ll i=3;i<=sqrtn;i+=2){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
vl mobius(ll n){
    //n以下の整数に対するメビウス関数の値の列挙(O(NloglogN))
    vl res(n+1,1);
    vl min_factor(n+1,-1);
    vb primedesu(n+1,true);
    primedesu[1]=false; min_factor[1]=1;
    repi(p,2,n+1){
        if(!primedesu[p]) continue;
        min_factor[p]=p;
        res[p]=-1;
        for(ll q=2*p;q<=n;q+=p){
            primedesu[q]=false;
            if(min_factor[q]==-1) min_factor[q]=p;
            if((q/p)%p==0) res[q]=0;
            else res[q]=-res[q];
        }
    }
    return res;
}
vector<pair<ll,char>> rle(string s){//ランレングス圧縮(数,文字)
    ll n=s.length();
    vector<pair<ll,char>> res;
    char pre=s[0];
    ll cnt=1;
    repi(i,1,n) {
        if(pre!=s[i]){
            res.push_back({cnt,pre});
            pre=s[i];
            cnt=1;
        }
        else cnt++;
    }
    res.push_back({cnt,pre});
    return res;
}
vl bfs(Graph G,ll s){//始点sからの距離
    ll n=G.size();
    vl dist(n,-1);
    quel que;
    dist[s]=0;
    que.push(s);
    while (!que.empty()) {
        ll v=que.front();
        que.pop();
        forv(nv,G[v]) {
            if (dist[nv]!=-1) continue;
            dist[nv]=dist[v]+1;
            que.push(nv);
        }
    }
    return dist;
}

template <typename T>
vector<T> jyu_nasi(vector<T> &a){//sortしてから！配列を重複なしにする
    a.erase(unique(all(a)),a.end());
    return a;
}

map<ll,ll> zaatu(vl &a,ll t){//O(NlogN) キーが返され、配列は圧縮済みのものになる
    map<ll,ll> poi;
    vl copy=a;
    sort(all(copy));
    copy=jyu_nasi(copy);
    vl res(a.size());
    rep(i,a.size()){
        if(t==0) poi[indexlb(copy,a[i])]=a[i];//t=0ならキーは圧縮、1ならキーは元の要素
        else poi[a[i]]=indexlb(copy,a[i]);
        res[i]=indexlb(copy,a[i]);
    }
    a=res;
    return poi;
}

vl ruisekiwa(vl a){//累積和とる
    ll n=a.size();
    vl res(n);
    res[0]=a[0];
    repi(i,1,n){
        res[i]=res[i-1]+a[i];
    }
    return res;
}
vl ruisekiwamod(vl a,ll mod){
    ll n=a.size();
    vl res(n);
    res[0]=a[0];
    repi(i,1,n){
        res[i]=res[i-1]+a[i];
        res[i]%=mod;
    }
    return res;
}

struct unionfind{
  vl p;
  unionfind(ll n):p(n,-1){}//rootなら-1*連結成分のサイズ
  ll root(ll x){
    if(p[x]<0){
      return x;
    } else{
      p[x]=root(p[x]);
      return p[x];
    }
  }
  ll size(ll x){
    return -p[root(x)];
  }
  bool same(ll x,ll y){
      return root(x)==root(y);
  }
  void merge(ll x,ll y){
    x=root(x);
    y=root(y);
    if(x==y) return;
    if(size(x)<size(y)){
        swap(x,y);
    }
    p[x]+=p[y];
    p[y]=x;
  }
  vvl groups(){
        ll _n=p.size();
        vl leader_buf(_n); vl group_size(_n);
        rep(i,_n){
            leader_buf[i]=root(i);
            group_size[leader_buf[i]]++;
        }
        vvl result(_n);
        rep(i,_n){
            result[i].reserve(group_size[i]);
        }
        rep(i,_n){
            result[leader_buf[i]].pb(i);
        }
        result.erase(
            remove_if(all(result),
                           [&](const vl& v) {return v.empty();}),
            result.end());
        return result;
    }
};

vl dijkstra(Graph2 &G,ll s){//sは始点  O(ElogV)
    //有向でも動くが単一始点であることに注意(扱いづらい)
    ll n=G.size();
    prq<pll,vector<pll>,greater<pll>> que;
    vl dst(n,1e18);
    dst[s]=0;
    que.push(pll(0,s));
    while(que.size()){
        ll d=que.top().fi;
        ll u=que.top().se;
        que.pop();
        if(dst[u]<d) continue;
        rep(i,G[u].size()){
            ll v=G[u][i].to;
            ll cost=G[u][i].leng;
            if(dst[v]>d+cost){
                dst[v]=d+cost;
                que.push(pll(dst[v],v));
            }
        }
    }
    return dst;
}

int main(){
    double a,b,c;
    cin>>a>>b>>c;
    bool ok=false;
    repi(i,abs(b-c)+1,b+c){
        if(b*b+i*i>=c*c){
        double x=(b*b-c*c+i*i)/(2*i);
        double y=i-x;/*
        setpre(x,12);
        setpre(y,12);//*/
        if(x<0||y<0) continue;
        for(double j=1;j<=x;j++){
            double z=sqrt(b*b+j*j-2*j*x);
            double w=(b*b+z*z-j*j)/(2*b*z);
            for(double f=1;f<=y;f++){
                double d=sqrt(c*c+f*f-2*f*y);
                double e=(c*c+d*d-f*f)/(2*c*d);/*
                if(i==4&&j==1&&f==1){
                    setpre(z,20);
                    setpre(w,20);
                    setpre(d,20);
                    setpre(e,20);
                }//*/
                if(abs(w-e)<=1e-5&&abs(x-j+y-f-a)<=1e-5){
                    ok=true;
                    break;
                }
            }
        }
        }
        else{
            double x=(-b*b+c*c-i*i)/(2*i);
            for(double j=1;j<i;j++){
                for(double f=1;f<i;f++){
                    double z=sqrt(b*b+j*j+2*j*x);
                    double w=(b*b+z*z-j*j)/(2*b*z);
                    double d=sqrt(b*b-x*x+i*i-2*i*f+f*f);
                    double e=(c*c+d*d-f*f)/(2*c*d);
                    if(abs(w-e)<=1e-5&&abs(i-j-f-a)<=1e-5){
                        ok=true;
                        break;
                    }
                }
            }
        }
    }
    YesNo(ok);
}
yukicoder

結果

ソースコード
