제출 #1281692

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281692		makmed1337	자리 배치 (IOI18_seats)	C++20	0 / 100	128 ms	16168 KiB

seats

#include "seats.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>

using namespace std;
#define all(a) begin(a), end(a)

struct SqrtDec {
    static constexpr int BLK = 1024;
    struct T {
        // vector<int> cnt;
        map<int, int> cnt;
        array<int, BLK> a;
        int lazy = 0;

        // T(int max_val) : cnt(max_val * 2 + 1), lazy(max_val) {}
        T() {
            fill(all(a), 0);
            cnt[0] = BLK;
        }

        void add(int d) { lazy += d; }

        void add(int i, int d) {
            --cnt[a[i]];
            ++cnt[a[i] += d];
        }

        int get(int x) { return cnt[x - lazy]; }

        int get(int i, int d) { return a[i] + lazy == d; }

        int gv(int i) { return a[i] + lazy; }
    };

    vector<T> blocks;
    // SqrtDec(int n, int mx) : blocks(n, T(mx)) {}

    void init(vector<int> a) {
        // assert(*max_element(all(a)) <= mx && *min_element(all(a)) >= 0);
        blocks.assign((a.size() + BLK - 1) / BLK, T{});
        for (int i = 0; i < a.size(); i++) {
            blocks[i / BLK].add(i % BLK, a[i]);
        }
    }

    void add(int l, int r, int d) {
        while (l % BLK && l <= r) {
            blocks[l / BLK].add(l % BLK, d);
            l++;
        }

        while (l + BLK <= r) {
            blocks[l / BLK].add(d);
            l += BLK;
        }

        while (l <= r) {
            blocks[l / BLK].add(l % BLK, d);
            l++;
        }
    }

    int get(int l, int r, int x) {
        int res = 0;
        while (l % BLK && l <= r) {
            res += blocks[l / BLK].get(l % BLK, x);
            l++;
        }

        while (l + BLK <= r) {
            res += blocks[l / BLK].get(x);
            l += BLK;
        }

        while (l <= r) {
            res += blocks[l / BLK].get(l % BLK, x);
            l++;
        }
        return res;
    }

    void print(int l, int r) {
        while (l <= r) {
            cerr << blocks[l / BLK].gv(l % BLK) << " ";
            l++;
        }
        cerr << "\n";
    }
};

int SZ;
SqrtDec sqdec;
vector<pair<int, int>> pos;
vector<vector<int>> index;

int get_delta(int neig) {
    if (neig == 2) {
        return -1;
    } else if (neig == 0) {
        return +1;
    }
    return 0;
}

int get_neig(pair<int, int> p, int t) {
    auto [y, x] = p;
    assert(y == 0);

    int neig = 0;
    if (x > 0) {
        neig += index[y][x - 1] <= t;
    }

    if (x + 1 < index[0].size()) {
        neig += index[y][x + 1] <= t;
    }

    return neig;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    assert(H == 1);

    SZ = H * W;

    index.assign(H, vector<int>(W, H * W));
    vector<int> cnt(SZ);
    int bords = 0;
    for (int i = 0; i < SZ; i++) {
        int y = R[i], x = C[i];
        pos.push_back({y, x});

        int neig = get_neig({y, x}, i);
        bords += get_delta(neig);
        cnt[i] = bords;
        index[y][x] = i;
    }
    sqdec.init(cnt);

    // sqdec.print(0, SZ - 1);
}

void unroll(pair<int, int> p) {
    auto [y, x] = p;
    vector<int> ts{index[y][x]};
    if (x >= 1) {
        ts.push_back(index[y][x - 1]);
    }
    if (x + 1 < index[0].size()) {
        ts.push_back(index[y][x + 1]);
    }

    for (auto t : ts) {
        auto p = pos[t];
        sqdec.add(t, SZ - 1, -get_neig(p, t));
    }
    index[y][x] = SZ;
}

void roll(pair<int, int> p, int val) {
    auto [y, x] = p;
    index[y][x] = val;
    vector<int> ts{index[y][x]};
    if (x >= 1) {
        ts.push_back(index[y][x - 1]);
    }
    if (x + 1 < index[0].size()) {
        ts.push_back(index[y][x + 1]);
    }

    for (auto t : ts) {
        auto p = pos[t];
        sqdec.add(t, SZ - 1, get_neig(p, t));
    }
}

void remove(pair<int, int> p) {
    unroll(p);
    roll(p, SZ);
}

void add(pair<int, int> p, int t) {
    unroll(p);
    roll(p, t);
}

int swap_seats(int a, int b) {
    assert(a != b);
    auto &pa = pos[a], &pb = pos[b];
    remove(pa);
    remove(pb);
    swap(pa, pb);

    // sqdec.print(0, SZ - 1);

    add(pa, a);
    add(pb, b);

    // cerr << "Index: ";
    // for (auto i : index[0]) {
    //     cerr << i << " ";
    // }
    // cerr << "\n";

    // sqdec.print(0, SZ - 1);
    return sqdec.get(0, SZ - 1, 1);
}

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp:99:21: warning: built-in function 'index' declared as non-function [-Wbuiltin-declaration-mismatch]
   99 | vector<vector<int>> index;
      |                     ^~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30