제출 #651894

#제출 시각아이디문제언어결과실행 시간메모리
651894ymmPark (BOI16_park)C++17
0 / 100
727 ms49784 KiB
#include <bits/stdc++.h> #define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x) #define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x) typedef long long ll; typedef std::pair<int, int> pii; typedef std::pair<ll , ll > pll; using namespace std; const int N = 2048; const int M = 100'010; vector<pair<pll,pii>> dis2; vector<pair<ll,int>> vis; int ans[N], vr[N], vent[N]; int par[N]; int rt(int v){return par[v]==v?v:(par[v]=rt(par[v]));} void unite(int v, int u) { v = rt(v); u = rt(u); par[u] = v; } ll Ox[N], Oy[N], Or[N]; ll W, H; int n, m; ll sqr(ll x){return x*x;} bool cmp (pll _x, pll _y) { pair<__int128, __int128> x = _x; pair<__int128, __int128> y = _y; auto mn = min(x.second, y.second); x.second -= mn; y.second -= mn; if (x.first != 0 && y.first != 0) { x = {4*sqr(x.second)*x.first, x.first + sqr(x.second)}; // 0, 1e18 y = {4*sqr(y.second)*y.first, y.first + sqr(y.second)}; // 1e36, 1e18 } if (x.first == 0) { x.second -= y.second; y.second = 0; if (x.second < 0) return 1; return sqr(x.second) < y.first; } else { y.second -= x.second; x.second = 0; if (y.second < 0) return 0; return x.first < sqr(y.second); } } bool cmp_wrap(const pair<pll,pii> &x, const pair<pll,pii> &y) { return cmp(x.first, y.first); } int main() { cin.tie(0) -> sync_with_stdio(false); cin >> n >> m; cin >> W >> H; Loop (i,0,n) cin >> Ox[i] >> Oy[i] >> Or[i]; Loop (i,0,m) { cin >> vr[i] >> vent[i]; --vent[i]; } Loop (i,0,n) { dis2.push_back({{0, Oy[i] - Or[i]}, {i+4, 0}}); dis2.push_back({{0, W - Ox[i] - Or[i]}, {i+4, 1}}); dis2.push_back({{0, H - Oy[i] - Or[i]}, {i+4, 2}}); dis2.push_back({{0, Ox[i] - Or[i]}, {i+4, 3}}); } Loop (i,0,n) Loop (j,i+1,n) { ll sdis = sqr(Ox[i] - Ox[j]) + sqr(Oy[i] - Oy[j]); ll dis = - Or[i] - Or[j]; dis2.push_back({{sdis, dis}, {i+4, j+4}}); } Loop (i,0,m) vis.push_back({vr[i], i}); sort(dis2.rbegin(), dis2.rend(), cmp_wrap); sort(vis.rbegin(), vis.rend()); iota(par, par+N, 0); while (vis.size()) { auto [r2, i] = vis.back(); vis.pop_back(); r2 *= 2; while (dis2.size() && cmp(dis2.back().first, {0, r2})) { auto [v, u] = dis2.back().second; unite(v, u); dis2.pop_back(); } int e = vent[i]; int s0 = rt(e+0 & 3); int s1 = rt(e+1 & 3); int s2 = rt(e+2 & 3); int s3 = rt(e+3 & 3); ans[i] |= (1 << (e+0 & 3)); if (s0 != s1 && s0 != s2 && s0 != s3) ans[i] |= (1 << (e+1 & 3)); if (s0 != s2 && s0 != s3 && s1 != s2 && s1 != s3) ans[i] |= (1 << (e+2 & 3)); if (s3 != s0 && s3 != s1 && s3 != s2) ans[i] |= (1 << (e+3 & 3)); } Loop (i,0,m) { Loop (j,0,4) if (ans[i] & (1 << j)) cout << j+1; cout << '\n'; } }

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

park.cpp: In function 'int main()':
park.cpp:99:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   99 |   int s0 = rt(e+0 & 3);
      |               ~^~
park.cpp:100:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  100 |   int s1 = rt(e+1 & 3);
      |               ~^~
park.cpp:101:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  101 |   int s2 = rt(e+2 & 3);
      |               ~^~
park.cpp:102:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  102 |   int s3 = rt(e+3 & 3);
      |               ~^~
park.cpp:103:21: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  103 |   ans[i] |= (1 << (e+0 & 3));
      |                    ~^~
park.cpp:105:22: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  105 |    ans[i] |= (1 << (e+1 & 3));
      |                     ~^~
park.cpp:107:22: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  107 |    ans[i] |= (1 << (e+2 & 3));
      |                     ~^~
park.cpp:109:22: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  109 |    ans[i] |= (1 << (e+3 & 3));
      |                     ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...