제출 #1044012

#제출 시각아이디문제언어결과실행 시간메모리
1044012alex_2008Naval battle (CEOI24_battle)C++14
0 / 100
7 ms604 KiB
#include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <map> #include <queue> typedef long long ll; using namespace std; const int N = 5e3 + 10; int a[N], x[N], y[N]; int dist[N][N]; char dir[N]; bool used[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> x[i] >> y[i] >> dir[i]; } priority_queue <pair<int, pair<int, int>>> Q; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { if (dir[i] == 'N') { if (dir[j] == 'W') { if (x[j] > x[i] && (x[j] - x[i]) == (y[i] - y[j])) { Q.push({ -(x[j] - x[i]), { i, j } }); } } else if (dir[j] == 'E') { if (x[j] < x[i] && (x[i] - x[j]) == (y[i] - y[j])) { Q.push({ -(x[i] - x[j]), { i, j } }); } } else if (dir[j] == 'S') { if (x[i] == x[j] && y[i] > y[j]) { Q.push({ -(y[i] - y[j]) / 2, { i, j } }); } } continue; } if (dir[i] == 'S') { if (dir[j] == 'W') { if (x[j] > x[i] && (x[j] - x[i]) == (y[j] - y[i])) { Q.push({ -(x[j] - x[i]), { i, j } }); } } else if (dir[j] == 'E') { if (x[j] < x[i] && (x[i] - x[j]) == (y[j] - y[i])) { Q.push({ -(x[i] - x[j]), { i, j } }); } } else if (dir[j] == 'N') { if (x[i] == x[j] && y[j] > y[i]) { Q.push({ -(y[j] - y[i]) / 2, { i, j } }); } } continue; } if (dir[i] == 'E') { if (dir[j] == 'N') { if (x[j] > x[i] && (x[j] - x[i]) == (y[j] - y[i])) { Q.push({ -(x[j] - x[i]), { i, j } }); } } else if (dir[j] == 'S') { if (x[j] > x[i] && (x[j] - x[i]) == (y[i] - y[j])) { Q.push({ -(x[j] - x[i]), { i, j } }); } } else if (dir[j] == 'W') { if (y[i] == y[j] && x[i] < x[j]) { Q.push({ -(x[j] - x[i]) / 2, { i, j } }); } } continue; } if (dir[i] == 'W') { if (dir[j] == 'N') { if (x[j] > x[i] && (x[i] - x[j]) == (y[j] - y[i])) { Q.push({ -(x[i] - x[j]), { i, j } }); } } else if (dir[j] == 'S') { if (x[j] > x[i] && (x[i] - x[j]) == (y[i] - y[j])) { Q.push({ -(x[i] - x[j]), { i, j } }); } } else if (dir[j] == 'E') { if (y[i] == y[j] && x[i] > x[j]) { Q.push({ -(x[i] - x[j]) / 2, { i, j } }); } } continue; } } } while (1) { if (Q.empty()) break; pair <int, pair<int, int>> t = Q.top(); vector <int> v; while (!Q.empty() && Q.top().first == t.first) { int x = Q.top().second.first, y = Q.top().second.second; if (!used[x] && !used[y]) { v.push_back(x); v.push_back(y); } Q.pop(); } for (auto it : v) { used[it] = true; } } for (int i = 1; i <= n; i++) { if (!used[i]) { cout << i << "\n"; } } }
#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...