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