結果

問題 No.742 にゃんにゃんにゃん　猫の挨拶
ユーザー ciel
提出日時 2018-10-07 11:09:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 7 ms / 2,500 ms
コード長 1,310 bytes
コンパイル時間 236 ms
コンパイル使用メモリ 39,808 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 14:09:48
合計ジャッジ時間 794 ms
ジャッジサーバーID
（参考情報） 		judge / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:34:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |         scanf("%d",&N);for(i=0;i<N;i++)scanf("%d",A+i);printf("%lld\n",merge_and_count(0,N));
      |         ~~~~~^~~~~~~~~
main.cpp:34:45: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |         scanf("%d",&N);for(i=0;i<N;i++)scanf("%d",A+i);printf("%lld\n",merge_and_count(0,N));
      |                                        ~~~~~^~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
int A[999999], W[999999];
long long merge_and_count(int l, int r) { // range [l,r)
    if (l+1 >= r) return 0; // empty
    if (l+2 == r) { // [l,r) == [l,l+1] 要素2つだけ
        if (A[l] <= A[l+1]) return 0; // 逆転はなし
        std::swap(A[l], A[l+1]);
        return 1; // 逆転一つ
    }
    int m = (l+r)/2; // [l,r) == [l,m) + [m,r)
    long long cl = merge_and_count(l, m); // 左半分を再帰的に数える
    long long cr = merge_and_count(m, r); // 右半分を再帰的に数える
    long long c = 0; // 左と右を混ぜるときの逆転数
    int i=l, j=m; // iは[l,m)を動き, jは[m,r)を動いて、
    int k=l; // 小さいものから W[k] に書き込む
    while (i<m && j<r) { // A[i]とA[j]を比べながら進む
        if (A[i] <= A[j]) W[k++] = A[i++]; // 左半分の方が小さく逆転なし
        else {
            W[k++] = A[j++];
            c += m-i; // 左半分の方が大きい、左半分で未処理の要素だけ飛び越える
        }
    }
    while (i<m) W[k++] = A[i++]; // 左半分が余った場合
    while (j<r) W[k++] = A[j++]; // 右半分が余った場合
    //assert(k == r);
    std::copy(W+l, W+r, A+l);
    return cl + cr + c;
}
int main(){
    int T,i,N;
    scanf("%d",&N);for(i=0;i<N;i++)scanf("%d",A+i);printf("%lld\n",merge_and_count(0,N));
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0