結果
問題 |
No.2519 Coins in Array
|
ユーザー |
|
提出日時 | 2023-10-27 22:36:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 1,869 bytes |
コンパイル時間 | 2,325 ms |
コンパイル使用メモリ | 207,624 KB |
最終ジャッジ日時 | 2025-02-17 15:28:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; pair<ll,vector<array<int,2>>>dfs(vector<ll> v){ assert(!v.empty()); if(v.size()==1){ return make_pair(v[0],vector<array<int,2>>()); } int N=v.size(); vector<array<int,2>>ret; ll m=1e18; for(int i=0;i<N;i++){ for(int j=i+1;j<N;j++){ vector v2(0,0ll); for(int k=0;k<N;k++){ if(k!=i&&k!=j)v2.push_back(v[k]); } if(gcd(v[i],v[j])!=1)v2.push_back(0); else v2.push_back(v[i]*v[j]-v[i]-v[j]+1); auto [n,rv]=dfs(v2); if(n<m){ m=n; rv.push_back({i+1,j+1}); ret=rv; } } } return make_pair(m,ret); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin>>N; vector A(N,0ll); int idx1=-1; for(int i=0;i<N;i++){ cin>>A[i]; if(A[i]==1){ idx1=i; } } if(idx1==-1){ if(N<4){ auto [m,v]=dfs(A); reverse(v.begin(),v.end()); cout<<m<<'\n'; for(auto i:v)cout<<i[0]<<' '<<i[1]<<'\n'; }else{ cout<<"0\n"; vector odd(0,0),even(0,0); for(int i=0;i<N;i++){ if(A[i]%2){ odd.push_back(i); }else{ even.push_back(i); } } while(even.size()<2){ int k1=odd.back(); odd.pop_back(); int k2=odd.back(); odd.pop_back(); for(int &i:even){ if(i>k1)i-=1; } for(int &i:even){ if(i>k2)i-=1; } even.push_back(odd.size()+even.size()); cout<<k1+1<<' '<<k2+1<<'\n'; } cout<<even[0]+1<<' '<<even[1]+1<<'\n'; for(int i=odd.size()+even.size()-1;i>1;i--){ cout<<i<<" 1\n"; } } }else{ cout<<"0\n"; if(idx1==0){ cout<<"1 2\n"; }else{ cout<<idx1+1<<" 1\n"; } for(int i=N-1;i>1;i--){ cout<<i<<" 1\n"; } } }