이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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', 'E'}, // neg_diag
{'W', '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 == 'E') {
int neg_diag = s.x - s.y;
int pos_diag = s.x + s.y;
lines[0][trans[neg_diag]].insert(s);
lines[2][trans[pos_diag]].insert(s);
} else {
int neg_diag = s.x - s.y;
int pos_diag = s.x + s.y;
lines[1][trans[neg_diag]].insert(s);
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();
continue;
}
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 == 'E') {
int neg_diag = s.x - s.y;
int pos_diag = s.x + s.y;
add_refreshers(s, lines[0][trans[neg_diag]], to_refresh, 0);
add_refreshers(s, lines[2][trans[pos_diag]], to_refresh, 2);
} else {
int neg_diag = s.x - s.y;
int pos_diag = s.x + s.y;
add_refreshers(s, lines[1][trans[neg_diag]], to_refresh, 1);
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";
}
컴파일 시 표준 에러 (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) {}
| ^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |