제출 #349411

#제출 시각아이디문제언어결과실행 시간메모리
349411sinamhdvPark (BOI16_park)C++11
100 / 100
1459 ms1644 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int mod = 1000 * 1000 * 1000 + 7; const int INF = 1000 * 1000 * 1000; const ll LINF = (ll)INF * INF; #ifdef DEBUG #define dbg(x) cout << #x << " = " << (x) << endl << flush; #define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; } #else #define dbg(x) ; #define dbgr(s, f) ; #endif #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod) #define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod) #define all(x) (x).begin(), (x).end() #define pb push_back #define mp make_pair #define fr first #define sc second #define endl '\n' #define MAXN 2020 int n, m; int w, h; int tx[MAXN], ty[MAXN], tr[MAXN]; int ans[5][5]; int cn; int comp[MAXN][MAXN]; int crad; inline bool olap(int a, int b) { if (a > n && b > n) return false; if (a > b) swap(a, b); if (b > n) // C - L { b -= n; int d; if (b == 1) d = ty[a] - crad; else if (b== 2) d = w - tx[a] - crad; else if (b == 3) d = h - ty[a] - crad; else if (b == 4) d = tx[a] - crad; return (tr[a] + crad > d); } else // C - C { int dx = abs(tx[a] - tx[b]); int dy = abs(ty[a] - ty[b]); int dr = tr[a] + tr[b] + 2 * crad; return ((ll)dr * dr > (ll)dx*dx + (ll)dy*dy); } } int ptr = 0; void dfs(int v) { comp[ptr][v] = cn; FOR(i, 1, n + 5) { if (comp[ptr][i] || !olap(v, i)) continue; dfs(i); } } inline void mkcomp(int r) { cn = 0; crad = r; FOR(i, 1, n + 5) { if (!comp[ptr][i]) { cn++; dfs(i); } } } inline bool check(int src, int dst) { if (abs(src - dst) == 2) { int x1 = src + n; int x2 = (src % 4) + 1 + n; int y1 = dst + n; int y2 = (dst % 4) + 1 + n; return (comp[ptr - 1][x1] != comp[ptr - 1][y2] && comp[ptr - 1][x1] != comp[ptr - 1][y1] && comp[ptr - 1][x2] != comp[ptr - 1][y1] && comp[ptr - 1][x2] != comp[ptr - 1][y2]); } else { if (src > dst) swap(src, dst); if (src == 1 && dst == 4) swap(src, dst); bool res = true; FOR(i, 1, 5) if (i != src) res &= (comp[ptr - 1][src + n] != comp[ptr - 1][i + n]); return res; } } int32_t main(void) { //fast_io; scanf("%d %d %d %d", &n, &m, &w, &h); FOR(i, 1, n + 1) { scanf("%d %d %d", tx + i, ty + i, tr + i); } /* while (true) { int s, d, r; cin >> r >> s >> d; cout << check(r, s, d) << endl << flush; } */ int qf[] = {1,1,1,2,2,3}; int qs[] = {2,3,4,3,4,4}; int l[] = {1, 1, 1, 1, 1, 1}; const int mx = INF; int r[] = {mx, mx, mx, mx, mx, mx}; int mid[6]; const int LOGN = 30; mkcomp(1); ptr++; FOR(i, 0, 6) { if (!check(qf[i], qs[i])) { l[i] = -1; r[i] = -1; } } FOR(bsi, 0, LOGN) { vector<int> rs; bool as[6]; FOR(i, 0, 6) { if (r[i] - l[i] > 1) { mid[i] = (l[i] + r[i]) >> 1; rs.pb(mid[i]); } } sort(all(rs)); rs.resize(unique(all(rs)) - rs.begin()); FOR(i, 0, (int)rs.size()) { mkcomp(rs[i]); ptr++; FOR(j, 0, 6) if (mid[j] == rs[i] && r[j] - l[j] > 1) as[j] = check(qf[j], qs[j]); } FOR(i, 0, 6) { if (r[i] - l[i] <= 1) continue; if (as[i]) l[i] = mid[i]; else r[i] = mid[i]; } dbgr(l, l + 6); dbgr(r, r + 6); dbgr(mid, mid + 6); } FOR(i, 0, 6) ans[qf[i]][qs[i]] = l[i]; /* FOR(e1, 1, 4) { FOR(e2, e1 + 1, 5) { int l = 1, r = INF + 10; if (!check(l, e1, e2)) { ans[e1][e2] = -1; continue; } while (r - l > 1) { int mid = (r + l) / 2; if (check(mid, e1, e2)) l = mid; else r = mid; } ans[e1][e2] = l; } }*/ while (m--) { int r, e; scanf("%d %d", &r, &e); char res[8] = {0,0,0,0,0,0,0,0}; char *ptr = res; FOR(i, 1, 5) { if (e == i || ans[e][i] >= r || ans[i][e] >= r) *ptr++ = (i + '0'); } puts(res); } return 0; }

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

park.cpp: In function 'int32_t main()':
park.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |  scanf("%d %d %d %d", &n, &m, &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |   scanf("%d %d %d", tx + i, ty + i, tr + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:235:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  235 |   scanf("%d %d", &r, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...