제출 #1080825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1080825		raphaelp	Naval battle (CEOI24_battle)	C++14	100 / 100	2860 ms	256352 KiB

Main

#include <bits/stdc++.h>
using namespace std;
struct ship
{
    int x, y;
    char type;
    int dirx, diry, i;
};
istream &operator>>(istream &is, ship &s)
{
    is >> s.x >> s.y >> s.type;
    if (s.type == 'E')
        s.dirx = 1, s.diry = 0;
    if (s.type == 'W')
        s.dirx = -1, s.diry = 0;
    if (s.type == 'S')
        s.dirx = 0, s.diry = 1;
    if (s.type == 'N')
        s.dirx = 0, s.diry = -1;
    return is;
}
bool operator<(ship a, ship b)
{
    if (a.x + a.y == b.x + b.y)
        return a.x < b.x;
    return a.x + a.y < b.x + b.y;
}
bool operator==(ship a, ship b) { return (a.x == b.x && a.y == b.y); }
struct colision
{
    int time;
    ship a, b;
};
bool operator<(colision a, colision b) { return a.time > b.time; }
bool operator==(colision a, colision b) { return (a.time == b.time && a.a == b.a && a.b == b.b); }
colision colide(ship a, ship b)
{
    if (a.type == b.type)
        return {1000000001, a, b};
    if (a.dirx == 0 && b.dirx == 0 && ((a.y < b.y && a.diry == 1) || (a.y > b.y && a.diry == -1)) && a.x == b.x)
        return {abs(a.y - b.y) / 2, a, b};
    if (a.diry == 0 && b.diry == 0 && ((a.x < b.x && a.dirx == 1) || (a.x > b.x && a.dirx == -1)) && a.y == b.y)
        return {abs(a.x - b.x) / 2, a, b};
    if (a.diry == 0)
        swap(a, b);
    if (((a.y < b.y && a.diry == 1) || (a.y > b.y && a.diry == -1)) && ((b.x < a.x && b.dirx == 1) || (b.x > a.x && b.dirx == -1)) && abs(a.x - b.x) == abs(a.y - b.y))
        return {abs(a.x - b.x), a, b};
    return {1000000001, a, b};
}
struct diagonal
{
    list<ship> ships;
    map<ship, list<ship>::iterator> M;
    priority_queue<colision> colisions;
    void push_back(ship s)
    {
        M[s] = ships.end();
        ships.push_back(s);
        M[s]--;
        auto pos = M[s];
        if (ships.size() == 1)
            return;
        pos--;
        colisions.push(colide(*pos, s));
    }
    colision get()
    {
        colision ans = colisions.top();
        colisions.pop();
        validate();
        return ans;
    }
    void validate()
    {
        while (!colisions.empty() && (!M.count(colisions.top().a) || !M.count(colisions.top().b)))
            colisions.pop();
    }
    void remove(ship s)
    {
        if (M.count(s) == 0)
            return;
        auto pos = M[s], pos2 = M[s];
        if (pos != ships.begin() && pos != ships.end())
            colisions.push(colide(*--pos, *++pos2));
        ships.erase(M[s]);
        M.erase(s);
        validate();
    }
};
struct ensemble
{
    int type = 1, type2 = 1;
    int hash(int x, int y) { return type2 * x + type * y; }
    map<int, diagonal> M;
    priority_queue<pair<colision, int>> colisions;
    void validate()
    {
        while (!colisions.empty() && (M[colisions.top().second].colisions.empty() || !(colisions.top().first == M[colisions.top().second].colisions.top())))
            colisions.pop();
    }
    colision get()
    {
        if (colisions.empty())
            return {1000000001};
        int pos = colisions.top().second;
        colision ans = M[pos].get();
        colisions.push({M[pos].colisions.top(), pos});
        validate();
        return ans;
    }
    void add(ship s)
    {
        int pos = hash(s.x, s.y);
        M[pos].push_back(s);
        if (!M[pos].colisions.empty())
            colisions.push({M[pos].colisions.top(), pos});
    }
    void remove(ship s)
    {
        int pos = hash(s.x, s.y);
        M[pos].remove(s);
        if (!M[pos].colisions.empty())
            colisions.push({M[pos].colisions.top(), pos});
        validate();
    }
};

int find(int x, vector<int> &r)
{
    if (x == r.size())
        return x;
    return (r[x] == x) ? x : r[x] = find(r[x], r);
}
int main()
{
    int N;
    cin >> N;
    int SW = 0, SE = 1, NW = 2, NE = 3, NS = 4, WE = 5;
    vector<ensemble> Tab(6);
    Tab[SW].type = -1, Tab[NE].type = -1, Tab[NS].type = 0, Tab[WE].type2 = 0;
    vector<ship> ships(N), V, H;
    for (int i = 0; i < N; i++)
    {
        cin >> ships[i];
        ships[i].i = i;
        ship s = ships[i];
        V.push_back(s);
        H.push_back(s);
    }
    sort(V.begin(), V.end(), [&](ship a, ship b)
         { return a.y < b.y; });
    sort(H.begin(), H.end(), [&](ship a, ship b)
         { return a.x < b.x; });
    for (int i = 0; i < N; i++)
    {
        if (V[i].dirx == 0)
            Tab[NS].add(V[i]);
        if (H[i].diry == 0)
            Tab[WE].add(H[i]);
        if (H[i].dirx == 1 || H[i].diry == 1)
            Tab[SE].add(H[i]);
        if (H[i].dirx == 1 || H[i].diry == -1)
            Tab[NE].add(H[i]);
        if (H[i].dirx == -1 || H[i].diry == -1)
            Tab[NW].add(H[i]);
        if (H[i].dirx == -1 || H[i].diry == 1)
            Tab[SW].add(H[i]);
    }
    vector<int> alive(N, 1000000001);
    while (true)
    {
        int minn = 1000000001;
        for (int i = 0; i < 6; i++)
            if (!Tab[i].colisions.empty())
                minn = min(minn, Tab[i].colisions.top().first.time);
        vector<ship> removed;
        if (minn == 1000000001)
            break;
        for (int i = 0; i < 6; i++)
        {
            while (!Tab[i].colisions.empty() && Tab[i].colisions.top().first.time == minn)
            {
                colision cur = Tab[i].get();
                alive[cur.a.i] = minn;
                alive[cur.b.i] = minn;
                removed.push_back(cur.a);
                removed.push_back(cur.b);
            }
        }
        while (!removed.empty())
        {
            for (int i = 0; i < 6; i++)
                Tab[i].remove(removed.back());
            removed.pop_back();
        }
    }
    for (int i = 0; i < N; i++)
        if (alive[i] == 1000000001)
            cout << i + 1 << '\n';
}

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

Main.cpp: In function 'int find(int, std::vector<int>&)':
Main.cpp:130:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     if (x == r.size())
      |         ~~^~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 11 / 11
• Subtask 5: 9 / 9
• Subtask 6: 30 / 30
• Subtask 7: 24 / 24