結果
問題 | No.1626 三角形の構築 |
ユーザー | 沙耶花 |
提出日時 | 2021-07-23 23:11:07 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,997 bytes |
コンパイル時間 | 4,567 ms |
コンパイル使用メモリ | 275,468 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-04-20 16:02:54 |
合計ジャッジ時間 | 7,234 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | AC | 5 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 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 103 ms
5,376 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 35 ms
5,376 KB |
testcase_13 | WA | - |
testcase_14 | AC | 54 ms
5,376 KB |
testcase_15 | AC | 36 ms
5,376 KB |
testcase_16 | WA | - |
testcase_17 | AC | 57 ms
5,376 KB |
testcase_18 | AC | 31 ms
5,376 KB |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 105 ms
5,376 KB |
testcase_23 | AC | 59 ms
5,376 KB |
testcase_24 | AC | 475 ms
5,376 KB |
testcase_25 | AC | 66 ms
5,376 KB |
testcase_26 | AC | 13 ms
5,376 KB |
ソースコード
#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); sort(Y.begin(),Y.end()); rep(i,Y.size()){ if(Y[i]>=T)break; for(int j=i;j<Y.size();j++){ //cout<<i<<','<<j<<endl; if(Y[j]>=T)break; long long x = S; x /= Y[i]; if(x<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]&A[1]&A[2]&1)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; }