結果

問題 No.2519 Coins in Array
ユーザー MasKoaTSMasKoaTS
提出日時 2023-09-03 16:20:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,101 bytes
コンパイル時間 2,211 ms
コンパイル使用メモリ 210,932 KB
最終ジャッジ日時 2025-02-16 18:25:19
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 34 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;


/* BIT: RAQ対応BIT
    初期値は a_1 = a_2 = ... = a_n = 0
    ・add(l,r,x): [l,r) に x を加算する
    ・sum(i): a_1 + a_2 + ... + a_i を計算する
    計算量は全て O(logn)
*/
template <typename T>
struct BIT {
    int n;             // 要素数
    vector<T> bit[2];  // データの格納先
    BIT(int n_) { init(n_); }
    void init(int n_) {
        n = n_ + 1;
        for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
    }

    void add_sub(int p, int i, T x) {
        for (int idx = i; idx < n; idx += (idx & -idx)) {
            bit[p][idx] += x;
        }
    }
    void add(int l, int r, T x) {  // [l,r) に加算
        add_sub(0, l, -x * (l - 1));
        add_sub(0, r, x * (r - 1));
        add_sub(1, l, x);
        add_sub(1, r, -x);
    }

    T sum_sub(int p, int i) {
        T s(0);
        for (int idx = i; idx > 0; idx -= (idx & -idx)) {
            s += bit[p][idx];
        }
        return s;
    }
    T sum(int i) {
        if(i <= 0){
            return 0;
        } 
        return sum_sub(0, i) + sum_sub(1, i) * i; 
    }

    T sum(int l, int r) { 
        return sum(r - 1) - sum(l - 1); 
    }

    T operator[](int k) { 
        return sum(k, k + 1); 
    }
};

ll f(ll x, ll y) {
	return (gcd(x, y) == 1) ? (x - 1) * (y - 1) : 0;
}


int main(){
    int n;  cin >> n;
    vector<ll> a(n);
    for(auto& x : a){
        cin >> x;
    }
    
    ll ans = 0;
    vector<pair<int, int> > ops(n - 1, pair<int, int>({}));
    if(n == 2){
        ans = f(a[0], a[1]);
        ops = { {1, 2} };
    }
    else if(n == 3){
        ans = f(f(a[0], a[1]), a[2]);
        ops = { {1, 2}, {1, 2} };
        ll t = f(f(a[0], a[2]), a[1]);
        if(t < ans){
            ans = t;
            ops = { {1, 3}, {1, 2} };
        } 
        t = f(f(a[1], a[2]), a[0]);
        if(t < ans){
            ans = t;
            ops = { {2, 3}, {1, 2} };
        }       
    }
    else{
        ans = 0;
        BIT<int> bt(n * 2 - 1);
        multimap<ll, int> mp = {};
        for(int i = 0; i < n; ++i){
            bt.add(i + 1, i + 2, i + 1);
            mp.insert({a[i], i + 1});
        }
        for(int k = 0; k < n - 1; ++k){
            pair<ll, int> pa1 = *(mp.begin());   mp.erase(mp.begin());
            pair<ll, int> pa2 = *(mp.begin());   mp.erase(mp.begin());
            // cout << k << endl;
            // cout << pa1.first << ' ' << pa1.second << endl;
            // cout << pa2.first << ' ' << pa2.second << endl;
            // cout << bt[pa1.second] << ' ' <<  bt[pa2.second] << endl;
            int x = bt[pa1.second], y = bt[pa2.second];
            ops[k] = {x, y};
            bt.add(pa1.second + 1, n * 2, -1);
            bt.add(pa2.second + 1, n * 2, -1);
            bt.add(n + k + 1, n + k + 2, n + k + 1);
            mp.insert({f(pa1.first, pa2.first), n + k + 1});
        }
    }

    cout << ans << endl;
    for(auto&[x, y] : ops){
        if(x > y){
            swap(x, y);
        }
        cout << x << ' ' << y << endl;
    }

    return 0;
}
0