제출 #1044284

#제출 시각아이디문제언어결과실행 시간메모리
1044284TsovakNaval battle (CEOI24_battle)C++17
6 / 100
3052 ms65428 KiB
// -------------------- Includes -------------------- // #define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #include <iostream> #include <iomanip> #include <cstdio> #include <stdio.h> #include <cstdlib> #include <stdlib.h> #include <array> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <math.h> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <vector> #include <stack> #include <queue> #include <deque> #include <bitset> #include <list> #include <iterator> #include <numeric> #include <complex> #include <tuple> #include <utility> #include <cassert> #include <assert.h> #include <climits> #include <limits.h> #include <ctime> #include <time.h> #include <random> #include <chrono> #include <fstream> using namespace std; // -------------------- Typedefs -------------------- // typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ld; // -------------------- Defines -------------------- // #define pr pair #define mpr make_pair #define ff first #define ss second #define mset multiset #define mmap multimap #define uset unordered_set #define umap unordered_map #define umset unordered_multiset #define ummap unordered_multimap #define pqueue priority_queue #define sz(x) (int((x).size())) #define len(x) (int((x).length())) #define all(x) (x).begin(), (x).end() #define clr(x) (x).clear() #define ft front #define bk back #define pf push_front #define pb push_back #define popf pop_front #define popb pop_back #define lb lower_bound #define ub upper_bound #define bs binary_search // -------------------- Constants -------------------- // const int MAX = int(1e9 + 5); const ll MAXL = ll(1e18 + 5); const ll MOD = ll(1e9 + 7); const ll MOD2 = ll(998244353); // -------------------- Functions -------------------- // void fastio() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); return; } void precision(int x) { cout << fixed << setprecision(x); return; } ll gcd0(ll a, ll b) { while (b) { a %= b; swap(a, b); } return a; } ll lcm0(ll a, ll b) { return a / gcd0(a, b) * b; } bool is_prime(ll a) { if (a == 1) return false; for (ll i = 2; i * i <= a; i++) if (a % i == 0) return false; return true; } bool is_square(ll a) { ll b = ll(sqrtl(ld(a))); return (b * b == a); } bool is_cube(ll a) { ll b = ll(cbrtl(ld(a))); return (b * b * b == a); } int digit_sum(ll a) { int sum = 0; while (a) { sum += int(a % 10); a /= 10; } return sum; } ll binpow(ll a, int b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll binpow_mod(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1) ans = (ans * a) % mod; b >>= 1; a = (a * a) % mod; } return ans; } ll factorial(int a) { ll ans = 1; for (int i = 2; i <= a; i++) ans *= ll(i); return ans; } ll factorial_mod(int a, ll mod) { ll ans = 1; for (int i = 2; i <= a; i++) ans = (ans * ll(i)) % mod; return ans; } // -------------------- Solution -------------------- // const pr<int, pr<int, int>> null = mpr(-1, mpr(-1, -1)); struct ship { int x, y; char d; vector<int> vo; }; const int N = 200005; ship a[N]; bool used[N]; int n; vector<pr<pr<int, pr<int, int>>, pr<int, int>>> v; vector<pr<int, int>> vv; pr<int, pr<int, int>> col(ship x, ship y) { if (x.d == y.d) return null; if (x.x == y.x) { if (x.d == 'E' || x.d == 'W' || y.d == 'E' || y.d == 'W') return null; if (x.y > y.y) swap(x, y); if (x.d == 'S' && y.d == 'N') return mpr((y.y - x.y) / 2, mpr(x.x, (x.y + y.y) / 2)); return null; } if (x.y == y.y) { if (x.d == 'N' || x.d == 'S' || y.d == 'N' || y.d == 'S') return null; if (x.x > y.x) swap(x, y); if (x.d == 'E' && y.d == 'W') return mpr((y.x - x.x) / 2, mpr((x.x + y.x) / 2, x.y)); return null; } if (x.x - x.y == y.x - y.y) { if (x.x > y.x) swap(x, y); if (x.d == 'E' && y.d == 'N') return mpr(y.x - x.x, mpr(y.x, x.y)); if (x.d == 'S' && y.d == 'W') return mpr(y.x - x.x, mpr(x.x, y.y)); return null; } if (x.x + x.y == y.x + y.y) { if (x.x > y.x) swap(x, y); if (x.d == 'N' && y.d == 'W') return mpr(y.x - x.x, mpr(x.x, y.y)); if (x.d == 'E' && y.d == 'S') return mpr(y.x - x.x, mpr(y.x, x.y)); return null; } return null; } map<int, vector<pr<int, int>>> mpx, mpy, mp11, mp12, mp21, mp22; void init() { int i, j; for (i = 1; i <= n; i++) { if (a[i].d == 'N') { mpx[a[i].x].pb(mpr(a[i].y, i)); mp11[a[i].x - a[i].y].pb(mpr(a[i].x, i)); mp21[a[i].x + a[i].y].pb(mpr(a[i].x, i)); } else if (a[i].d == 'S') { mpx[a[i].x].pb(mpr(a[i].y, i)); mp12[a[i].x - a[i].y].pb(mpr(a[i].x, i)); mp22[a[i].x + a[i].y].pb(mpr(a[i].x, i)); } else if (a[i].d == 'E') { mpy[a[i].y].pb(mpr(a[i].x, i)); mp11[a[i].x - a[i].y].pb(mpr(a[i].x, i)); mp22[a[i].x + a[i].y].pb(mpr(a[i].x, i)); } else { mpy[a[i].y].pb(mpr(a[i].x, i)); mp12[a[i].x - a[i].y].pb(mpr(a[i].x, i)); mp21[a[i].x + a[i].y].pb(mpr(a[i].x, i)); } } return; } set<pr<pr<int, pr<int, int>>, pr<int, int>>> st; void solve() { int i, j; cin >> n; for (i = 1; i <= n; i++) cin >> a[i].x >> a[i].y >> a[i].d; init(); for (auto p : mpx) sort(all(mpx[p.ff])); for (auto p : mpy) sort(all(mpy[p.ff])); for (auto p : mp11) sort(all(mp11[p.ff])); for (auto p : mp12) sort(all(mp12[p.ff])); for (auto p : mp21) sort(all(mp21[p.ff])); for (auto p : mp22) sort(all(mp22[p.ff])); stack<int> st; for (auto p : mpx) { while (!st.empty()) st.pop(); for (i = 0; i < sz(p.ss); i++) { if (a[p.ss[i].ss].d == 'N' && !st.empty() && a[st.top()].d == 'S') { a[p.ss[i].ss].vo.pb(st.top()); a[st.top()].vo.pb(p.ss[i].ss); st.pop(); } else st.push(p.ss[i].ss); } } for (auto p : mpy) { while (!st.empty()) st.pop(); for (i = 0; i < sz(p.ss); i++) { if (a[p.ss[i].ss].d == 'W' && !st.empty() && a[st.top()].d == 'E') { a[p.ss[i].ss].vo.pb(st.top()); a[st.top()].vo.pb(p.ss[i].ss); st.pop(); } else st.push(p.ss[i].ss); } } for (auto p : mp11) { while (!st.empty()) st.pop(); for (i = 0; i < sz(p.ss); i++) { if (a[p.ss[i].ss].d == 'N' && !st.empty() && a[st.top()].d == 'E') { a[p.ss[i].ss].vo.pb(st.top()); a[st.top()].vo.pb(p.ss[i].ss); st.pop(); } else st.push(p.ss[i].ss); } } for (auto p : mp12) { while (!st.empty()) st.pop(); for (i = 0; i < sz(p.ss); i++) { if (a[p.ss[i].ss].d == 'W' && !st.empty() && a[st.top()].d == 'S') { a[p.ss[i].ss].vo.pb(st.top()); a[st.top()].vo.pb(p.ss[i].ss); st.pop(); } else st.push(p.ss[i].ss); } } for (auto p : mp21) { while (!st.empty()) st.pop(); for (i = 0; i < sz(p.ss); i++) { if (a[p.ss[i].ss].d == 'W' && !st.empty() && a[st.top()].d == 'N') { a[p.ss[i].ss].vo.pb(st.top()); a[st.top()].vo.pb(p.ss[i].ss); st.pop(); } else st.push(p.ss[i].ss); } } for (auto p : mp22) { while (!st.empty()) st.pop(); for (i = 0; i < sz(p.ss); i++) { if (a[p.ss[i].ss].d == 'S' && !st.empty() && a[st.top()].d == 'E') { a[p.ss[i].ss].vo.pb(st.top()); a[st.top()].vo.pb(p.ss[i].ss); st.pop(); } else st.push(p.ss[i].ss); } } pr<int, pr<int, int>> e; for (i = 1; i <= n; i++) { if (sz(a[i].vo) > 3) assert(false); for (auto j : a[i].vo) if (col(a[i], a[j]) == null) assert(false); } for (i = 1; i < n; i++) { for (j = 0; j < sz(a[i].vo); j++) { if (a[i].vo[j] < i) continue; e = col(a[i], a[a[i].vo[j]]); if (e == null) assert(false); v.pb(mpr(e, mpr(i, a[i].vo[j]))); } } sort(all(v)); int ind = 0; while (ind < sz(v)) { clr(vv); e = v[ind].ff; vv.pb(v[ind].ss); for (i = ind + 1; i < sz(v); i++) { if (v[i].ff != e) break; if (used[v[i].ss.ff] || used[v[i].ss.ss]) continue; vv.pb(v[i].ss); } for (i = 0; i < sz(vv); i++) used[vv[i].ff] = used[vv[i].ss] = true; while (i < sz(v) && (used[v[i].ss.ff] || used[v[i].ss.ss])) i++; ind = i; } for (i = 1; i <= n; i++) if (!used[i]) cout << i << "\n"; return; } void precalc() { return; } int main() { fastio(); precalc(); int tests = 1, tc; //cin >> tests; for (tc = 1; tc <= tests; tc++) { solve(); } return 0; } /* # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # */

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

Main.cpp: In function 'void init()':
Main.cpp:253:9: warning: unused variable 'j' [-Wunused-variable]
  253 |  int i, j;
      |         ^
#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...