結果
問題 | No.1626 三角形の構築 |
ユーザー | 沙耶花 |
提出日時 | 2021-07-24 01:20:43 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,109 bytes |
コンパイル時間 | 5,061 ms |
コンパイル使用メモリ | 275,940 KB |
実行使用メモリ | 11,632 KB |
最終ジャッジ日時 | 2024-04-20 16:09:32 |
合計ジャッジ時間 | 24,746 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
10,624 KB |
testcase_01 | AC | 833 ms
5,376 KB |
testcase_02 | AC | 6 ms
5,376 KB |
testcase_03 | AC | 4 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 4 ms
5,376 KB |
testcase_07 | AC | 643 ms
5,376 KB |
testcase_08 | AC | 1,032 ms
5,376 KB |
testcase_09 | AC | 1,442 ms
5,376 KB |
testcase_10 | AC | 743 ms
5,376 KB |
testcase_11 | AC | 1,226 ms
5,376 KB |
testcase_12 | AC | 278 ms
5,376 KB |
testcase_13 | AC | 293 ms
5,376 KB |
testcase_14 | AC | 866 ms
5,376 KB |
testcase_15 | AC | 474 ms
5,376 KB |
testcase_16 | AC | 836 ms
5,376 KB |
testcase_17 | AC | 814 ms
5,376 KB |
testcase_18 | AC | 514 ms
5,376 KB |
testcase_19 | AC | 904 ms
5,376 KB |
testcase_20 | AC | 1,082 ms
5,376 KB |
testcase_21 | AC | 885 ms
5,376 KB |
testcase_22 | AC | 1,617 ms
5,376 KB |
testcase_23 | AC | 962 ms
5,376 KB |
testcase_24 | TLE | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 map<long long,int> get(long long n){ map<long long,int> ret; for(long long i=2;i*i<=n;i++){ while(n%i==0){ ret[i]++; n/=i; } } if(n!=1)ret[n]++; return ret; } void Out(vector<array<long long,3>> A){ rep(i,A.size())sort(A[i].begin(),A[i].end()); sort(A.begin(),A.end()); A.erase(unique(A.begin(),A.end()),A.end()); cout<<A.size()<<endl; rep(i,A.size()){ cout<<A[i][0]<<' '<<A[i][1]<<' '<<A[i][2]<<endl; } } void dfs(vector<long long> &Y,vector<pair<long long,int>> &Ps,int pos,long long cur){ //cout<<pos<<','<<cur<<endl; if(pos==Ps.size()){ Y.push_back(cur); return; } for(int i=0;i<=Ps[pos].second;i++){ dfs(Y,Ps,pos+1,cur); cur *= Ps[pos].first; } } void solve(){ long long S,T; cin>>S>>T; vector<array<long long,3>> ans; map<long long,int> s = get(S); for(auto &a:s){ a.second *= 2; } s[2] += 4; { auto t = get(T); for(auto a:t){ if(s[a.first]<a.second){ Out(ans); return; } s[a.first] -= a.second; } } S = 1LL; vector<pair<long long,int>> Ps; for(auto a:s){ if(a.second>0){ Ps.emplace_back(a.first,a.second); } rep(j,a.second)S *= a.first; } vector<long long> Y; dfs(Y,Ps,0,1LL); { int tt = Y.size(); rep(i,tt){ Y.push_back(Y[i]*-1); } } sort(Y.begin(),Y.end()); rep(i,Y.size()){ for(int j=i;j<Y.size();j++){ long long x = S; x /= Y[i]; if(abs(x)<abs(Y[j]))break; if(x%Y[j]!=0)continue; x/=Y[j]; if(x>=T)continue; array<long long,3> A = {T-Y[i],T-Y[j],T-x}; sort(A.begin(),A.end()); if(A[0]<=0)continue; if(A[2]>1000000000)continue; if(A[0]%2)continue; if(A[1]%2)continue; if(A[2]%2)continue; A[0]/=2; A[1]/=2; A[2]/=2; if(A[0]+A[1]+A[2]!=T)continue; if(A[2]>=A[1]+A[0])continue; ans.push_back(A); } } Out(ans); } int main(){ int _t; cin>>_t; rep(_,_t){ solve(); } return 0; }