結果

問題 No.2519 Coins in Array
ユーザー MasKoaTSMasKoaTS
提出日時 2023-09-03 16:20:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,101 bytes
コンパイル時間 2,461 ms
コンパイル使用メモリ 219,496 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-06-23 12:24:35
合計ジャッジ時間 12,091 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 WA -
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 2 ms
6,944 KB
testcase_23 AC 480 ms
22,016 KB
testcase_24 AC 548 ms
22,144 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 544 ms
22,016 KB
testcase_28 AC 545 ms
22,016 KB
testcase_29 AC 558 ms
22,016 KB
testcase_30 AC 492 ms
20,096 KB
testcase_31 AC 73 ms
6,944 KB
testcase_32 AC 243 ms
12,416 KB
testcase_33 AC 366 ms
16,256 KB
testcase_34 AC 162 ms
9,344 KB
testcase_35 AC 340 ms
15,104 KB
testcase_36 AC 124 ms
8,064 KB
testcase_37 AC 56 ms
6,944 KB
testcase_38 AC 266 ms
13,184 KB
testcase_39 AC 143 ms
8,704 KB
testcase_40 AC 457 ms
22,016 KB
権限があれば一括ダウンロードができます

ソースコード

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