mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #319 (Div. 1) C. Points on Plane

Codeforces Round #319 (Div. 1) の Virtual Participation をやりました。

A しか解けなくて死んだので結果的には寝坊してレートを得した感じです。

解法

割と単純です。

まず x 軸を 1000 ごとに分けます。

そして, その 1000 ごとの区切りごとに, y 軸について頂点をソートします。

偶数番目の区画は y を小さい方から大きい方にたどっていき, 奇数番目の区画は y を大きい方から小さい方にたどっていきます。

イメージとしてはこんな感じですね。これが求める答えです。
f:id:mayokoex:20150911192143j:plain

なぜこれで良いのかを考えます。

まず y 軸の移動を考えると, これは 10^6 の移動を最大で 10^3 回やるので, 移動量は 10^9 です。
また, x 軸の移動を考えると, まず各区切り内では最大 10^3 ずつ移動し, これは最大 10^6 回繰り返されるので移動量はたかだか 10^9 です。また区切りと区切りの間では最大 2*10^3 の移動を最高 10^3 回行うので, 合計の移動量はたかだか 2*10^9 + 2*10^6 です。

よって, 問題文にあるような制限以内には答えが求められることがわかります。

struct P {
    int x, y, id;
    P() {}
    bool operator<(const P& rhs) {return y < rhs.y;}
};

const int MAXN = 1000100;
P ps[MAXN];
vector<P> pss[1010];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &ps[i].x, &ps[i].y);
        ps[i].id = i;
        pss[ps[i].x/1000].push_back(ps[i]);
    }
    for (int i = 0; i <= 1000; i++) {
        sort(pss[i].begin(), pss[i].end());
        if (i%2) reverse(pss[i].begin(), pss[i].end());
    }
    for (int i = 0; i <= 1000; i++) {
        for (P el : pss[i]) printf("%d ", el.id+1);
    }
    printf("\n");
    return 0;
}