제출 #1044052

#제출 시각아이디문제언어결과실행 시간메모리
1044052alex_2008Naval battle (CEOI24_battle)C++14
46 / 100
341 ms26288 KiB
#include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <map> #include <queue> #include <stack> 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 ind[N]; bool cmp(int a, int b) { if (x[a] != x[b]) return x[a] > x[b]; if (y[a] != y[b]) return y[b] > y[a]; } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> x[i] >> y[i] >> dir[i]; } if (n <= 5000) { 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[i] > x[j] && (x[i] - x[j]) == (y[j] - y[i])) { Q.push({ -(x[i] - x[j]), { i, j } }); } } else if (dir[j] == 'S') { if (x[i] > x[j] && (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"; } } return 0; } map <int, stack<int>> mp; for (int i = 1; i <= n; i++) { ind[i] = i; } sort(ind + 1, ind + n + 1, cmp); for (int i = 1; i <= n; i++) { if (dir[ind[i]] == 'S') { mp[x[ind[i]] + y[ind[i]]].push(ind[i]); } else { if (mp[x[ind[i]] + y[ind[i]]].empty()) { cout << ind[i] << "\n"; } else mp[x[ind[i]] + y[ind[i]]].pop(); } } for (auto it : mp) { while (!it.second.empty()) { cout << it.second.top() << "\n"; it.second.pop(); } } }

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

Main.cpp: In function 'bool cmp(int, int)':
Main.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
   19 | }
      | ^
#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...