結果
問題 | 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";}}}