Submission #1068480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068480		faruk	Naval battle (CEOI24_battle)	C++17	100 / 100	2212 ms	400420 KiB

Main

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

map<int, int> get_compression(vector<int> vals) {
    map<int, int> out;
    sort(all(vals));
    vals.erase(unique(all(vals)), vals.end());
    for (int i = 0; i < vals.size(); i++)
        out[vals[i]] = i;
    return out;
}

struct ship {
    char c;
    int x, y, idx;
    ship() {}
    ship(char c, int x, int y) : x(x), y(y), c(c) {}

    bool operator<(const ship& b) const {
        return pii(x, y) < pii(b.x, b.y);
    }

    bool operator==(const ship&b) const {
        return idx == b.idx;
    }
};

struct deathh {
    int tim;
    ship a, b;
    deathh() {}
    deathh(ship a, ship b, int tim) : a(a), b(b), tim(tim) {}

    bool operator<(const deathh& b) const {
        return tim > b.tim;
    }
};

// if typ < 4
int dist_diag(ship a, ship b) {
    return abs(a.x - b.x);
}

// if typ >= 4
int dist_same(ship a, ship b) {
    return max(
        abs(a.x - b.x) / 2,
        abs(a.y - b.y) / 2
    );
}

vector<pair<char, char> > collisions = {
        {'S', 'W'}, // neg_diag
        {'E', 'N'}, // neg_diag
        {'E', 'S'}, // pos_diag
        {'N', 'W'}, // pos_diag
        {'S', 'N'}, // parni y
        {'S', 'N'}, // neparni y
        {'E', 'W'}, // parni x
        {'E', 'W'}  // neparni x
    };
const int first_straight = 4;
const int num_lin_typ = 8;

priority_queue<deathh> hits;
void try_contrib(set<ship>::iterator me, int id, set<ship> &my) {
    if (me->c != collisions[id].first)
        return;
    if (next(me) == my.end())
        return;
    if (next(me)->c != collisions[id].second)   
        return;
    deathh to_add(*me, *next(me), 0);
    if (id < first_straight)
        to_add.tim = dist_diag(to_add.a, to_add.b);
    else
        to_add.tim = dist_same(to_add.a, to_add.b);
    hits.push(to_add);
}

struct helper {
    set<ship>::iterator a;
    int id;
    set<ship>& id2;
    helper(int id, set<ship> &id2, set<ship>::iterator a) : id(id), id2(id2), a(a) {}
};

void add_refreshers(ship s, set<ship> &my, vector<helper> &refreshers, int id) {
    auto me = my.find(s);
    if (me != my.begin())   
        refreshers.push_back(helper(id, my, prev(me)));
    my.erase(me);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> vals;
    vector<ship> guys(n);
    for (int i = 0; i < n; i++)  
    {
        cin >> guys[i].x >> guys[i].y >> guys[i].c;
        guys[i].idx = i;
        vals.push_back(guys[i].x);
        vals.push_back(guys[i].y);

        vals.push_back(guys[i].x + guys[i].y);
        vals.push_back(guys[i].x - guys[i].y);
    }
    map<int, int> trans = get_compression(vals);
    
    vector<vector<set<ship> > > lines(num_lin_typ, vector<set<ship>>(trans.size() + 1));

    for (ship s : guys) {
        if (s.c == 'S' || s.c == 'W') {
            int neg_diag = s.x - s.y;
            lines[0][trans[neg_diag]].insert(s);
        } else {
            int neg_diag = s.x - s.y;
            lines[1][trans[neg_diag]].insert(s);
        }
        if (s.c == 'E' || s.c == 'S') {
            int pos_diag = s.x + s.y;
            lines[2][trans[pos_diag]].insert(s);
        }
        else {
            int pos_diag = s.x + s.y;
            lines[3][trans[pos_diag]].insert(s);
        }

        if (s.c == 'S' || s.c == 'N') {
            int parity = s.y % 2;
            lines[4 + parity][trans[s.x]].insert(s);
        } else {
            int parity = s.x % 2;
            lines[6 + parity][trans[s.y]].insert(s);
        }
    }
    
    for (int i = 0; i < num_lin_typ; i++) {
        for (set<ship> &one_line : lines[i]) {
            for (auto ite = one_line.begin(); ite != one_line.end(); ite++)
                try_contrib(ite, i, one_line);
        }
    }

    set<ship> dead;
    while (!hits.empty()) {
        while (!hits.empty()) {
            deathh curr = hits.top();
            if (dead.count(curr.a) || dead.count(curr.b))
                hits.pop();
            else
                break;
        }
        if (hits.empty())
            break;
        int curr_tim = hits.top().tim;
        vector<ship> to_die;
        while (!hits.empty()) {
            deathh curr = hits.top();
            if (dead.count(curr.a) ||dead.count(curr.b))
                hits.pop();
            else if (curr.tim == curr_tim) 
            {
                to_die.push_back(curr.a);
                to_die.push_back(curr.b);
                hits.pop();
            }
            else
                break;
        }
        sort(all(to_die));
        to_die.erase(unique(all(to_die)), to_die.end());
        vector<helper> to_refresh;
        for (ship s : to_die) {
            if (s.c == 'S' || s.c == 'W') {
                int neg_diag = s.x - s.y;
                add_refreshers(s, lines[0][trans[neg_diag]], to_refresh, 0);
            } else {
                int neg_diag = s.x - s.y;
                add_refreshers(s, lines[1][trans[neg_diag]], to_refresh, 1);
            }
            if (s.c == 'E' || s.c == 'S') {
                int pos_diag = s.x + s.y;
                add_refreshers(s, lines[2][trans[pos_diag]], to_refresh, 2);
            }
            else {
                int pos_diag = s.x + s.y;
                add_refreshers(s, lines[3][trans[pos_diag]], to_refresh, 3);
            }

            if (s.c == 'S' || s.c == 'N') {
                int parity = s.y % 2;
                add_refreshers(s, lines[4 + parity][trans[s.x]], to_refresh, 4 + parity);
            } else {
                int parity = s.x % 2;
                add_refreshers(s, lines[6 + parity][trans[s.y]], to_refresh, 6 + parity);
            }
            dead.insert(s);
        }

        for (auto &[ite, id, my_set] : to_refresh) {
            if (dead.count(*ite))
                continue;
            try_contrib(ite, id, my_set);
        }
    }

    set<ship> out(all(guys));
    for (ship s : dead)
        out.erase(s);
    for (ship s : out)
        cout << s.idx + 1 << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'std::map<int, int> get_compression(std::vector<int>)':
Main.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 0; i < vals.size(); i++)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In constructor 'ship::ship(char, int, int)':
Main.cpp:21:12: warning: 'ship::y' will be initialized after [-Wreorder]
   21 |     int x, y, idx;
      |            ^
Main.cpp:20:10: warning:   'char ship::c' [-Wreorder]
   20 |     char c;
      |          ^
Main.cpp:23:5: warning:   when initialized here [-Wreorder]
   23 |     ship(char c, int x, int y) : x(x), y(y), c(c) {}
      |     ^~~~
Main.cpp: In constructor 'deathh::deathh(ship, ship, int)':
Main.cpp:36:13: warning: 'deathh::b' will be initialized after [-Wreorder]
   36 |     ship a, b;
      |             ^
Main.cpp:35:9: warning:   'int deathh::tim' [-Wreorder]
   35 |     int tim;
      |         ^~~
Main.cpp:38:5: warning:   when initialized here [-Wreorder]
   38 |     deathh(ship a, ship b, int tim) : a(a), b(b), tim(tim) {}
      |     ^~~~~~
Main.cpp: In constructor 'helper::helper(int, std::set<ship>&, std::set<ship>::iterator)':
Main.cpp:90:16: warning: 'helper::id2' will be initialized after [-Wreorder]
   90 |     set<ship>& id2;
      |                ^~~
Main.cpp:88:25: warning:   'std::set<ship>::iterator helper::a' [-Wreorder]
   88 |     set<ship>::iterator a;
      |                         ^
Main.cpp:91:5: warning:   when initialized here [-Wreorder]
   91 |     helper(int id, set<ship> &id2, set<ship>::iterator a) : id(id), id2(id2), a(a) {}
      |     ^~~~~~

• 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