제출 #1103775

#제출 시각아이디문제언어결과실행 시간메모리
1103775ShadowSharkNaval battle (CEOI24_battle)C++17
100 / 100
878 ms94248 KiB
#include <bits/stdc++.h> using namespace std; #define piii pair<int, pair<int, int>> const int maxN = 2e5 + 5; vector<int> hor, ver, dg1_en, dg1_sw, dg2_es, dg2_nw; set<pair<int, int>> H[maxN], V[maxN], D1_EN[maxN], D1_SW[maxN], D2_ES[maxN], D2_NW[maxN]; struct point { int x, y; char type; } p[maxN]; int tick[maxN]; priority_queue<piii, vector<piii>, greater<piii>> pq; void del(int id) { int pos; /// remove D1_EN if (p[id].type == 'E' || p[id].type == 'N') { pos = lower_bound(dg1_en.begin(), dg1_en.end(), p[id].x - p[id].y) - dg1_en.begin(); D1_EN[pos].erase(D1_EN[pos].find({p[id].x, id})); auto it = D1_EN[pos].lower_bound({p[id].x, id}); if (it != D1_EN[pos].end()) { auto it2 = it; it2--; auto [num1, id1] = *it2; auto [num2, id2] = *it; char t1 = p[id1].type, t2 = p[id2].type; if (t1 == 'E' && t2 == 'N') pq.push({num2 - num1, {id1, id2}}); } } else { /// remove D1_SW pos = lower_bound(dg1_sw.begin(), dg1_sw.end(), p[id].x - p[id].y) - dg1_sw.begin(); D1_SW[pos].erase(D1_SW[pos].find({p[id].x, id})); auto it = D1_SW[pos].lower_bound({p[id].x, id}); if (it != D1_SW[pos].end()) { auto it2 = it; it2--; auto [num1, id1] = *it2; auto [num2, id2] = *it; char t1 = p[id1].type, t2 = p[id2].type; if (t1 == 'S' && t2 == 'W') pq.push({num2 - num1, {id1, id2}}); } } /// remove D2_ES if (p[id].type == 'E' || p[id].type == 'S') { pos = lower_bound(dg2_es.begin(), dg2_es.end(), p[id].x + p[id].y) - dg2_es.begin(); D2_ES[pos].erase(D2_ES[pos].find({p[id].x, id})); auto it = D2_ES[pos].lower_bound({p[id].x, id}); if (it != D2_ES[pos].end()) { auto it2 = it; it2--; auto [num1, id1] = *it2; auto[num2, id2] = *it; char t1 = p[id1].type, t2 = p[id2].type; if (t1 == 'E' && t2 == 'S') pq.push({num2 - num1, {id1, id2}}); } } else { pos = lower_bound(dg2_nw.begin(), dg2_nw.end(), p[id].x + p[id].y) - dg2_nw.begin(); D2_NW[pos].erase(D2_NW[pos].find({p[id].x, id})); auto it = D2_NW[pos].lower_bound({p[id].x, id}); if (it != D2_NW[pos].end()) { auto it2 = it; it2--; auto [num1, id1] = *it2; auto[num2, id2] = *it; char t1 = p[id1].type, t2 = p[id2].type; if (t1 == 'N' && t2 == 'W') pq.push({num2 - num1, {id1, id2}}); } } /// remove H or V if (p[id].type == 'E' || p[id].type == 'W') { pos = lower_bound(hor.begin(), hor.end(), p[id].y) - hor.begin(); H[pos].erase(H[pos].find({p[id].x, id})); auto it = H[pos].lower_bound({p[id].x, id}); if (it != H[pos].end()) { auto it2 = it; it2--; auto [num1, id1] = *it2; auto [num2, id2] = *it; char t1 = p[id1].type, t2 = p[id2].type; if (t1 == 'E' && t2 == 'W') pq.push({(num2 - num1) / 2, {id1, id2}}); } } else { pos = lower_bound(ver.begin(), ver.end(), p[id].x) - ver.begin(); V[pos].erase(V[pos].find({p[id].y, id})); auto it = V[pos].lower_bound({p[id].y, id}); if (it != V[pos].end()) { auto it2 = it; it2--; auto [num1, id1] = *it2; auto [num2, id2] = *it; char t1 = p[id1].type, t2 = p[id2].type; if (t1 == 'S' && t2 == 'N') pq.push({(num2 - num1) / 2, {id1, id2}}); } } } void compress(vector<int> &a) { if (a.size() > 0) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> p[i].x >> p[i].y >> p[i].type; if (p[i].type == 'E' || p[i].type == 'W') hor.push_back(p[i].y); /// - else ver.push_back(p[i].x); /// | if (p[i].type == 'E' || p[i].type == 'N') dg1_en.push_back(p[i].x - p[i].y); else dg1_sw.push_back(p[i].x - p[i].y); if (p[i].type == 'E' || p[i].type == 'S') dg2_es.push_back(p[i].x + p[i].y); else dg2_nw.push_back(p[i].x + p[i].y); } compress(hor); compress(ver); compress(dg1_en); compress(dg1_sw); compress(dg2_es); compress(dg2_nw); for (int i = 1; i <= n; i++) { int pos; /// hor if (p[i].type == 'E' || p[i].type == 'W') { pos = lower_bound(hor.begin(), hor.end(), p[i].y) - hor.begin(); H[pos].insert({p[i].x, i}); } else { /// ver pos = lower_bound(ver.begin(), ver.end(), p[i].x) - ver.begin(); V[pos].insert({p[i].y, i}); } /// dg1 if (p[i].type == 'E' || p[i].type == 'N') { pos = lower_bound(dg1_en.begin(), dg1_en.end(), p[i].x - p[i].y) - dg1_en.begin(); D1_EN[pos].insert({p[i].x, i}); } else { pos = lower_bound(dg1_sw.begin(), dg1_sw.end(), p[i].x - p[i].y) - dg1_sw.begin(); D1_SW[pos].insert({p[i].x, i}); } /// dg2 if (p[i].type == 'E' || p[i].type == 'S') { pos = lower_bound(dg2_es.begin(), dg2_es.end(), p[i].x + p[i].y) - dg2_es.begin(); D2_ES[pos].insert({p[i].x, i}); } else { pos = lower_bound(dg2_nw.begin(), dg2_nw.end(), p[i].x + p[i].y) - dg2_nw.begin(); D2_NW[pos].insert({p[i].x, i}); } } /// Consider d2 for (int i = 0; i < dg2_es.size(); i++) { auto it = D2_ES[i].begin(); it++; while (it != D2_ES[i].end()) { auto it2 = it; it2--; auto [num1, id1] = *it2; auto [num2, id2] = *it; char t1 = p[id1].type, t2 = p[id2].type; if (t1 == 'E' && t2 == 'S') pq.push({num2 - num1, {id1, id2}}); it++; } } for (int i = 0; i < dg2_nw.size(); i++) { auto it = D2_NW[i].begin(); it++; while (it != D2_NW[i].end()) { auto it2 = it; it2--; auto [num1, id1] = *it2; auto [num2, id2] = *it; char t1 = p[id1].type, t2 = p[id2].type; if (t1 == 'N' && t2 == 'W') pq.push({num2 - num1, {id1, id2}}); it++; } } /// Consider d1 for (int i = 0; i < dg1_en.size(); i++) { auto it = D1_EN[i].begin(); it++; for ( ; it != D1_EN[i].end(); it++) { auto it2 = it; it2--; auto [num1, id1] = *it2; auto [num2, id2] = *it; char t1 = p[id1].type, t2 = p[id2].type; if (t1 == 'E' && t2 == 'N') pq.push({num2 - num1, {id1, id2}}); } } for (int i = 0; i < dg1_sw.size(); i++) { auto it = D1_SW[i].begin(); it++; for ( ; it != D1_SW[i].end(); it++) { auto it2 = it; it2--; auto [num1, id1] = *it2; auto [num2, id2] = *it; char t1 = p[id1].type, t2 = p[id2].type; if (t1 == 'S' && t2 == 'W') pq.push({num2 - num1, {id1, id2}}); } } /// Consider hor for (int i = 0; i < hor.size(); i++) { auto it = H[i].begin(); it++; for ( ; it != H[i].end(); it++) { auto it2 = it; it2--; auto [num1, id1] = *it2; auto [num2, id2] = *it; char t1 = p[id1].type, t2 = p[id2].type; if (t1 == 'E' && t2 == 'W') pq.push({(num2 - num1) / 2, {id1, id2}}); } } /// Consider ver for (int i = 0; i < ver.size(); i++) { auto it = V[i].begin(); it++; for ( ; it != V[i].end(); it++) { auto it2 = it; it2--; auto [num1, id1] = *it2; auto [num2, id2] = *it; char t1 = p[id1].type, t2 = p[id2].type; if (t1 == 'S' && t2 == 'N') pq.push({(num2 - num1) / 2, {id1, id2}}); } } while (pq.size() > 0) { auto it = pq.top(); pq.pop(); int hel = it.first, x = it.second.first, y = it.second.second; if (tick[x] && tick[y]) continue; if (!tick[x] && !tick[y]) { tick[x] = tick[y] = hel; del(x); del(y); continue; } if (tick[x] == hel) { tick[y] = hel; del(y); continue; } if (tick[y] == hel) { tick[x] = hel; del(x); continue; } } vector<int> res; res.clear(); for (int i = 1; i <= n; i++) if (!tick[i]) res.push_back(i); for (auto v: res) cout << v << '\n'; return 0; }

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

Main.cpp: In function 'int main()':
Main.cpp:165:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     for (int i = 0; i < dg2_es.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
Main.cpp:177:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for (int i = 0; i < dg2_nw.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
Main.cpp:190:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |     for (int i = 0; i < dg1_en.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
Main.cpp:201:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |     for (int i = 0; i < dg1_sw.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
Main.cpp:213:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |     for (int i = 0; i < hor.size(); i++) {
      |                     ~~^~~~~~~~~~~~
Main.cpp:225:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |     for (int i = 0; i < ver.size(); i++) {
      |                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...