結果
問題 | No.2519 Coins in Array |
ユーザー |
|
提出日時 | 2023-10-27 21:53:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 60 ms / 2,000 ms |
コード長 | 2,158 bytes |
コンパイル時間 | 1,071 ms |
コンパイル使用メモリ | 81,584 KB |
実行使用メモリ | 13,100 KB |
最終ジャッジ日時 | 2024-09-25 14:00:48 |
合計ジャッジ時間 | 5,490 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
ソースコード
#include<iostream>#include<vector>#include<cassert>using namespace std;long long gcd(long long a,long long b){while(b){long long t=a%b;a=b;b=t;}return a;}long long f(long long x,long long y){long long g=gcd(x,y);if(g>=2)return 0LL;x--,y--;assert(x==0||y==0||x<=(long long)1e18/y);return x*y;}vector<pair<int,int> >ans;long long solve(vector<long long>A){if(A.size()==1)return A[0];int zeroi=-1,onei=-1;vector<int>EV,OD;for(int i=0;i<A.size();i++){if(A[i]==0)zeroi=i;else if(A[i]==1)onei=i;else{if(A[i]%2==0)EV.push_back(i);else OD.push_back(i);}}if(zeroi!=-1){if(zeroi!=A.size()-1){ans.push_back(make_pair(zeroi,A.size()-1));A.pop_back();A.erase(A.begin()+zeroi);A.push_back(0);return solve(A);}for(int i=A.size()-1;i--;){ans.push_back(make_pair(i,i+1));}return 0LL;}if(onei!=-1){if(onei!=A.size()-1){ans.push_back(make_pair(onei,A.size()-1));A.pop_back();A.erase(A.begin()+onei);A.push_back(0);return solve(A);}for(int i=A.size()-1;i--;){ans.push_back(make_pair(i,i+1));}return 0LL;}if(EV.size()>=2){ans.push_back(make_pair(EV[0],EV[1]));A.erase(A.begin()+EV[1]);A.erase(A.begin()+EV[0]);A.push_back(0);return solve(A);}if(EV.size()==1&&OD.size()>=2||OD.size()>=4){long long x=OD[0],y=OD[1];ans.push_back(make_pair(OD[0],OD[1]));A.push_back(f(A[OD[0]],A[OD[1]]));A.erase(A.begin()+OD[1]);A.erase(A.begin()+OD[0]);return solve(A);}assert(A.size()<=3);if(A.size()==2){ans.push_back(make_pair(0,1));return f(A[0],A[1]);}long long x=A[0],y=A[1],z=A[2];long long X=f(f(x,y),z),Y=f(f(y,z),x),Z=f(f(z,x),y);if(X<=Y&&X<=Z)ans.push_back(make_pair(0,1));else if(Y<=X&&Y<=Z)ans.push_back(make_pair(1,2));else ans.push_back(make_pair(0,2));ans.push_back(make_pair(0,1));return min(min(X,Y),Z);}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin>>N;vector<long long>A(N);for(int i=0;i<N;i++)cin>>A[i];cout<<solve(A)<<"\n";for(pair<int,int>p:ans)cout<<p.first+1<<" "<<p.second+1<<"\n";}