結果
問題 | No.2555 Intriguing Triangle |
ユーザー | eq_K |
提出日時 | 2023-12-01 02:03:50 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 13,499 bytes |
コンパイル時間 | 4,848 ms |
コンパイル使用メモリ | 174,592 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-26 15:30:11 |
合計ジャッジ時間 | 4,603 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 52 ms
5,376 KB |
testcase_12 | AC | 66 ms
5,376 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 23 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 224 ms
5,376 KB |
testcase_21 | AC | 222 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | WA | - |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 53 ms
5,376 KB |
testcase_27 | AC | 82 ms
5,376 KB |
testcase_28 | AC | 11 ms
5,376 KB |
testcase_29 | AC | 24 ms
5,376 KB |
ソースコード
/* #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; } double ssqrt(double x){ double left{}, right{ x }, mid{}; if( x < 1 ) right = 1; while( right - left > 1e-7) { mid = ( left + right ) / 2.0; if( mid * mid > x ) { right = mid; } else { left = mid; } } return mid; } int main(){ double a,b,c; cin>>a>>b>>c; bool ok=false; repi(i,abs(b-c)+1,b+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=ssqrt(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=ssqrt(c*c+f*f-2*f*y); double e=(c*c+d*d-f*f)/(2*c*d);/* if(i==9&&j==1&&f==6){ setpre(z,20); setpre(w,20); setpre(d,20); setpre(e,20); }//*/ if(abs(w-e)<=1e-7&&abs(x-j+y-f-a)<=1e-7){ ok=true; break; } } } } YesNo(ok); }