제출 #1044143

#제출 시각아이디문제언어결과실행 시간메모리
1044143VahanAbrahamNaval battle (CEOI24_battle)C++14
37 / 100
3084 ms195768 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string> #include <algorithm> #include <cstring> #include <cstdio> #include <sstream> #include <map> #include <stack> #include <set> #include <queue> #include <list> #include <unordered_set> #include <unordered_map> #include <math.h> #include <bitset> #include <cmath> #include <vector> #include <iomanip> #include <random> #include <chrono> #include <cassert> using namespace std; #define ll long long #define fr first #define sc second #define pb push_back #define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout); ll gcd(ll a, ll b) { if (a == 0 || b == 0) { return max(a, b); } if (a <= b) { return gcd(a, b % a); } else { return gcd(a % b, b); } } ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; } const int N = 5005; const ll oo = 100000000000000000, MOD = 1000000007; struct NODE { int x, y, x1, y1; char d; }; NODE a[N], ner[N]; bool ok[N]; ll timer[N][N]; void solve() { int n; cin >> n; int mx = 0; for (int i = 1; i <= n; ++i) { char c; cin >> a[i].x >> a[i].y >> a[i].d; if (a[i].d == 'N') { a[i].x1 = 0; a[i].y1 = -1; } if (a[i].d == 'S') { a[i].x1 = 0; a[i].y1 = 1; } if (a[i].d == 'W') { a[i].x1 = -1, a[i].y1 = 0; } if (a[i].d == 'E') { a[i].x1 = 1, a[i].y1 = 0; } ner[i] = a[i]; mx = max(mx, a[i].x); mx = max(mx, a[i].y); } while (1) { ll mn = oo; for (int i = 1; i < n; ++i) { for (int j = i + 1; j <= n; ++j) { if (ok[i] != 1 && ok[j] != 1) { if (a[i].d == a[j].d) { continue; } timer[i][j] = oo; if (a[i].d == 'S' && a[j].d == 'N') { if (a[i].x == a[j].x && a[i].y < a[j].y) { int tm = abs(a[i].y - a[j].y) / 2; timer[i][j] = tm; } } if (a[i].d == 'S' && a[j].d == 'E') { if (a[i].y < a[j].y && a[j].x < a[i].x) { int xx = a[i].x, yy = a[j].y; int dist1 = abs(xx - a[i].x) + abs(yy - a[i].y); int dist2 = abs(xx - a[j].x) + abs(yy - a[j].y); if (dist1 == dist2) { timer[i][j] = dist1; } } } if (a[i].d == 'S' && a[j].d == 'W') { if (a[i].y < a[j].y && a[j].x > a[i].x) { int xx = a[i].x, yy = a[j].y; int dist1 = abs(xx - a[i].x) + abs(yy - a[i].y); int dist2 = abs(xx - a[j].x) + abs(yy - a[j].y); if (dist1 == dist2) { timer[i][j] = dist1; } } } if (a[i].d == 'N' && a[j].d == 'S') { if (a[i].x == a[j].x && a[i].y > a[j].y) { int tm = abs(a[i].y - a[j].y) / 2; timer[i][j] = tm; } } if (a[i].d == 'N' && a[j].d == 'E') { if (a[i].y > a[j].y && a[j].x < a[i].x) { int xx = a[i].x, yy = a[j].y; int dist1 = abs(xx - a[i].x) + abs(yy - a[i].y); int dist2 = abs(xx - a[j].x) + abs(yy - a[j].y); if (dist1 == dist2) { timer[i][j] = dist1; } } } if (a[i].d == 'N' && a[j].d == 'W') { if (a[i].y > a[j].y && a[j].x > a[i].x) { int xx = a[i].x, yy = a[j].y; int dist1 = abs(xx - a[i].x) + abs(yy - a[i].y); int dist2 = abs(xx - a[j].x) + abs(yy - a[j].y); if (dist1 == dist2) { timer[i][j] = dist1; } } } if (a[i].d == 'W' && a[j].d == 'E') { if (a[i].y == a[j].y && a[i].x > a[j].x) { timer[i][j] = abs(a[i].x - a[j].x) / 2; } } if (a[i].d == 'W' && a[j].d == 'S') { if (a[i].y > a[j].y && a[i].x > a[j].x) { int xx = a[j].x, yy = a[i].y; int dist1 = abs(xx - a[i].x) + abs(yy - a[i].y); int dist2 = abs(xx - a[j].x) + abs(yy - a[j].y); if (dist1 == dist2) { timer[i][j] = dist1; } } } if (a[i].d == 'W' && a[j].d == 'N') { if (a[i].y < a[j].y && a[i].x > a[j].x) { int xx = a[j].x, yy = a[i].y; int dist1 = abs(xx - a[i].x) + abs(yy - a[i].y); int dist2 = abs(xx - a[j].x) + abs(yy - a[j].y); if (dist1 == dist2) { timer[i][j] = dist1; } } } if (a[i].d == 'E' && a[j].d == 'W') { if (a[i].y == a[j].y && a[j].x > a[i].x) { timer[i][j] = abs(a[i].x - a[j].x) / 2; } } if (a[i].d == 'E' && a[j].d == 'S') { if (a[i].y > a[j].y && a[i].x < a[j].x) { int xx = a[j].x, yy = a[i].y; int dist1 = abs(xx - a[i].x) + abs(yy - a[i].y); int dist2 = abs(xx - a[j].x) + abs(yy - a[j].y); if (dist1 == dist2) { timer[i][j] = dist1; } } } if (a[i].d == 'E' && a[j].d == 'N') { if (a[i].y < a[j].y && a[i].x < a[j].x) { int xx = a[j].x, yy = a[i].y; int dist1 = abs(xx - a[i].x) + abs(yy - a[i].y); int dist2 = abs(xx - a[j].x) + abs(yy - a[j].y); if (dist1 == dist2) { timer[i][j] = dist1; } } } mn = min(mn, timer[i][j]); } } } if (mn == oo) { break; } set<int> s; for (int i = 1; i < n; ++i) { for (int j = i+1; j <= n; ++j) { if (timer[i][j] == mn && ok[i] != 1 && ok[j] != 1) { s.insert(i); s.insert(j); } } } for (auto it : s) { ok[it] = 1; } } for (int i = 1; i <= n; ++i) { if (ok[i] == 0) { cout << i << endl; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //US int tt = 1; //cin >> tt; while (tt--) { solve(); } }

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

Main.cpp: In function 'void solve()':
Main.cpp:66:14: warning: unused variable 'c' [-Wunused-variable]
   66 |         char c;
      |              ^
#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...