C - Ants on a Circle

C - Ants on a Circle

解法

蟻なのでぶつかる際にすれ違う事にして、番号を交換すればよさそう

最終的な位置集合は分かり、かつ 1< 2 <3 ...なので、一匹でも答えがわかれば解ける

位置は1< 2 <3で常に一定なので、 交換する番号は自分-1である

よって最終的な番号は自分-すれ違った回数

全てのiについてすれ違う回数を求めればいい

Submission #4562270 - AtCoder Grand Contest 013

void solve() {
    int l, t;
    cin >> n >> l >> t;
    vi d;
    na2(a, d, n);
    rep(i, n)if (d[i] == 2)d[i] = -1;
    vi pos(n);
    vi poss;
    rep(i, n)pos[i] = mod(a[i] + d[i] * t, l), poss += pos[i];
    sort(poss);
    //ゼッケンを交換すると考えると
    //そのたびに+-1しか変わらない

    //ぶつからない
    int s = -1;
    rep(i, n) {
        if (d[i] == -1) {
            s = i;
            brk;
        }
    }
    if (s == -1) {
        cout << pos << endl;
    } else {
        int lastp = pos[s];
        int rb = a[s];
        rep(i, n) {
            if (d[i] == 1) {
                int lb = a[i];
                if (lb > rb)lb -= l;
                int nt2 = t * 2 - (rb - lb);
                if (nt2 >= 0) {
                    s--;
                    s -= nt2 / l;
                }
            }
        }
        s = mod(s, n);
        vi res(n);
        int ind = lowerIndex(poss, lastp);
        rep(i, n) {
            int p = (s + i) % n;
            res[p] = poss[(ind + i) % n];
        }
        out(res);
    }
}