結果

問題 No.2519 Coins in Array
ユーザー RubikunRubikun
提出日時 2023-10-27 21:42:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 53 ms / 2,000 ms
コード長 3,128 bytes
コンパイル時間 2,300 ms
コンパイル使用メモリ 214,356 KB
実行使用メモリ 7,960 KB
最終ジャッジ日時 2023-10-27 21:42:43
合計ジャッジ時間 6,344 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 2 ms
4,348 KB
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 2 ms
4,348 KB
testcase_15 AC 1 ms
4,348 KB
testcase_16 AC 1 ms
4,348 KB
testcase_17 AC 2 ms
4,348 KB
testcase_18 AC 2 ms
4,348 KB
testcase_19 AC 2 ms
4,348 KB
testcase_20 AC 2 ms
4,348 KB
testcase_21 AC 2 ms
4,348 KB
testcase_22 AC 2 ms
4,348 KB
testcase_23 AC 53 ms
7,960 KB
testcase_24 AC 48 ms
7,960 KB
testcase_25 AC 1 ms
4,348 KB
testcase_26 AC 2 ms
4,348 KB
testcase_27 AC 48 ms
6,896 KB
testcase_28 AC 51 ms
6,896 KB
testcase_29 AC 52 ms
6,896 KB
testcase_30 AC 45 ms
6,748 KB
testcase_31 AC 9 ms
4,348 KB
testcase_32 AC 24 ms
5,036 KB
testcase_33 AC 37 ms
6,424 KB
testcase_34 AC 19 ms
4,536 KB
testcase_35 AC 30 ms
5,280 KB
testcase_36 AC 14 ms
4,348 KB
testcase_37 AC 8 ms
4,348 KB
testcase_38 AC 27 ms
5,108 KB
testcase_39 AC 16 ms
4,360 KB
testcase_40 AC 42 ms
7,960 KB
権限があれば一括ダウンロードができます

ソースコード

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