結果

問題 No.2519 Coins in Array
ユーザー RubikunRubikun
提出日時 2023-10-27 21:42:36
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 55 ms / 2,000 ms
コード長 3,128 bytes
コンパイル時間 2,465 ms
コンパイル使用メモリ 213,924 KB
実行使用メモリ 7,932 KB
最終ジャッジ日時 2024-09-25 13:48:07
合計ジャッジ時間 6,721 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;

ll gcd(ll a,ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}

ll f(ll a,ll b){
    if(a==0||b==0) return 0;
    if(gcd(a,b)>1) return 0;
    return (a-1)*(b-1);
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    vector<ll> A(N);
    for(int i=0;i<N;i++) cin>>A[i];
    
    if(N==2){
        cout<<f(A[0],A[1])<<endl;
        cout<<1<<" "<<2<<endl;
    }else if(N==3){
        pair<ll,ll> ans=mp(1LL<<60,-1);
        chmin(ans,mp(f(f(A[0],A[1]),A[2]),0LL));
        chmin(ans,mp(f(f(A[0],A[2]),A[1]),1LL));
        chmin(ans,mp(f(f(A[1],A[2]),A[0]),2LL));
        
        cout<<ans.fi<<"\n";
        if(ans.se==0){
            cout<<1<<" "<<2<<endl;
            cout<<1<<" "<<2<<endl;
        }
        if(ans.se==1){
            cout<<1<<" "<<3<<endl;
            cout<<1<<" "<<2<<endl;
        }
        if(ans.se==2){
            cout<<2<<" "<<3<<endl;
            cout<<1<<" "<<2<<endl;
        }
    }else{
        vector<pair<int,int>> ans;
        cout<<0<<endl;
        
        int zero=-1;
        for(int i=0;i<si(A);i++){
            if(A[i]==0) zero=i;
        }
        if(zero==-1){
            vector<int> S,T;
            while(1){
                for(int i=0;i<si(A);i++){
                    if(A[i]&1) S.push_back(i);
                    else T.push_back(i);
                }
                
                if(si(T)>=2) break;
                
                ll x=f(A[S[0]],A[S[1]]);
                ans.push_back(mp(S[0],S[1]));
                A.erase(A.begin()+S[1]);
                A.erase(A.begin()+S[0]);
                A.push_back(x);
                
                S.clear();
                T.clear();
            }
            
            for(int i=0;i<si(A);i++){
                if(A[i]==0) zero=i;
            }
            
            if(zero==-1){
                ll x=f(A[T[0]],A[T[1]]);
                ans.push_back(mp(T[0],T[1]));
                A.erase(A.begin()+T[1]);
                A.erase(A.begin()+T[0]);
                A.push_back(x);
                
                for(int i=0;i<si(A);i++){
                    if(A[i]==0) zero=i;
                }
            }
            
        }
        
        if(si(A)>1){
            for(int i=0;i<si(A);i++){
                if(i!=zero){
                    ans.push_back(mp(i,zero));
                    A.pop_back();
                    break;
                }
            }
        }
        
        while(si(A)>1){
            ans.push_back(mp(si(A)-2,si(A)-1));
            A.pop_back();
        }
        
        for(auto [a,b]:ans) cout<<a+1<<" "<<b+1<<"\n";
    }
}
0