#526332 (C++17) No.1150 シュークリームゲーム（Easy）

提出ソース

結果

問題	No.1150 シュークリームゲーム（Easy）
ユーザー	Shibuyap
提出日時	2020-08-07 23:08:11
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	47 ms / 2,000 ms
コード長	6,676 bytes
コンパイル時間	2,131 ms
コンパイル使用メモリ	204,344 KB
実行使用メモリ	9,612 KB
最終ジャッジ日時	2023-10-25 04:20:32
合計ジャッジ時間	4,869 ms
ジャッジサーバーID （参考情報）	judge11 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	3 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	2 ms 4,348 KB
testcase_16	AC	2 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	38 ms 9,444 KB
testcase_23	AC	39 ms 9,460 KB
testcase_24	AC	36 ms 9,384 KB
testcase_25	AC	38 ms 9,428 KB
testcase_26	AC	42 ms 9,540 KB
testcase_27	AC	43 ms 9,556 KB
testcase_28	AC	45 ms 9,604 KB
testcase_29	AC	37 ms 9,408 KB
testcase_30	AC	40 ms 9,492 KB
testcase_31	AC	39 ms 9,456 KB
testcase_32	AC	38 ms 9,440 KB
testcase_33	AC	40 ms 9,496 KB
testcase_34	AC	41 ms 9,540 KB
testcase_35	AC	42 ms 9,560 KB
testcase_36	AC	43 ms 9,588 KB
testcase_37	AC	44 ms 9,604 KB
testcase_38	AC	37 ms 9,416 KB
testcase_39	AC	38 ms 9,420 KB
testcase_40	AC	40 ms 9,484 KB
testcase_41	AC	43 ms 9,568 KB
testcase_42	AC	33 ms 9,612 KB
testcase_43	AC	34 ms 9,612 KB
testcase_44	AC	47 ms 9,612 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef pair<int,int> P;
typedef long long int ll;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}

const int MAX_N = 1 << 19;

// セグメント木を持つグローバル配列
ll nn, dat[2 * MAX_N - 1];
ll INF = 1001001001001001001;
// 初期化
void init(int n_){
    // n_が小さいときの変な挙動を防ぐ
    if(n_ < 10)n_ = 10;
    // 簡単のため要素数を2のべき乗に
    nn = 1;
    while(nn < n_)nn *= 2;

    // 全ての値をINT_MAXに
    for(int i = 0; i < 2 * nn - 1; i++)dat[i] = INF;
}

// k番目の値(0-indexed)をaに変更
void update(int k, ll a){
    // 葉の接点
    k += nn - 1;
    dat[k] = a;
    // 登りながら更新
    while(k > 0){
        k = (k - 1) / 2;
        dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
}

// [a,b)の最小値を求める
// 後ろのほうの引数は、計算の簡単のための引数。
// kは節点の番号、l, rはその節点が[l, r)に対応づいていることを表す。
// したがって、外からはquery(a, b, 0, 0, nn)として呼ぶ。
ll query(int a, int b, int k, int l, int r){
    // [a, b)と[l, r)が交差しなければ、INT_MAX
    if (r <= a || b <= l)return INF;

    // [a, b)が[l, r)を完全に含んでいれば、この節点の値
    if (a <= l && r <= b)return dat[k];
    else {
        // そうでなければ、2つの子の最小値
        ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
}


int main(){
    int n, s, t;
    cin >> n >> s >> t;
    s--; t--;

    init(n*2);

    ll a[n];
    ll sum = 0;
    rep(i,n){
        cin >> a[i];
        sum += a[i];
    } 
    int f[n] = {};
    ll x = 0, y = 0;
    int ss = s, tt = t;
    if(n % 2 == 1){
        if(s < t){
            while(true){
                if(f[ss])break;
                x += a[ss];
                f[ss] = 1;
                ss = (ss+1)%n;
                if(f[tt])break;
                y += a[tt];
                f[tt] = 1;
                tt = (tt+n-1)%n;
            }
            ss = (s+n-1)%n;
            tt = (t+1)%n;
            while(true){
                if(f[ss])break;
                x += a[ss];
                f[ss] = 1;
                ss = (ss+n-1)%n;
                if(f[tt])break;
                y += a[tt];
                f[tt] = 1;
                tt = (tt+1)%n;
            }
        }else{
            while(true){
                if(f[ss])break;
                x += a[ss];
                f[ss] = 1;
                ss = (ss+n-1)%n;
                if(f[tt])break;
                y += a[tt];
                f[tt] = 1;
                tt = (tt+1)%n;
            }
            ss = (s+1)%n;
            tt = (t+n-1)%n;
            while(true){
                if(f[ss])break;
                x += a[ss];
                f[ss] = 1;
                ss = (ss+1)%n;
                if(f[tt])break;
                y += a[tt];
                f[tt] = 1;
                tt = (tt+n-1)%n;
            }
        }
    }else{
        if(abs(s-t)%2==1){
            if(s < t){
                while(true){
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+n-1)%n;
                }
                ss = (s+n-1)%n;
                tt = (t+1)%n;
                while(true){
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+n-1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+1)%n;
                }
            }else{
                while(true){
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+n-1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+1)%n;
                }
                ss = (s+1)%n;
                tt = (t+n-1)%n;
                while(true){
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+n-1)%n;
                }
            }
        }else{
            ll aa, bb;
            if(s < t){
                while(true){
                    if(ss == tt) break;
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+n-1)%n;
                }
                aa = a[ss];
                ss = (s+n-1)%n;
                tt = (t+1)%n;
                while(true){
                    if(ss==tt)break;
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+n-1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+1)%n;
                }
                bb = a[ss];
            }else{
                while(true){
                    if(ss == tt) break;
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+n-1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+1)%n;
                }
                aa = a[ss];
                ss = (s+1)%n;
                tt = (t+n-1)%n;
                while(true){
                    if(ss == tt) break;
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+n-1)%n;
                }
                bb = a[ss];
            }
            x += max(aa,bb);
            y += min(aa,bb);
        }
    }

    cout << x - y << endl;
    return 0;
}

yukicoder

結果

テストケース

ソースコード