| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 651894 |
2022-10-20T12:27:42 Z |
ymm |
Park (BOI16_park) |
C++17 |
|
727 ms |
49784 KB |
#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';
}
}
Compilation message
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
727 ms |
49784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
727 ms |
49784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
