| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 377206 |
2021-03-13T10:13:40 Z |
gustason |
Wish (LMIO19_noras) |
C++14 |
|
1 ms |
364 KB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int INF = 1e9 + 5;
int n, r;
vector<pair<int, int>> a;
vector<pair<int, int>> dir;
vector<int> best;
vector<pair<int, int>> fr;
bool inside(int x, int y) {
if (x == r && y == 0) return true;
if (x == -r && y == 0) return true;
if (x == 0 && y == r) return true;
if (x == 0 && y == -r) return true;
int rr = r;
if (x >= -(rr-1) && x <= (rr-1) && y >= -(rr-1) && y <= (rr-1)) return true;
return false;
}
int getP(int x, int x0, int d) {
int ans = ceil((double) (x - x0) / d);
if (ans < 0) return -1;
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
map<int, int> mp;
cin >> n >> r;
a.resize(n);
dir.resize(n);
best.assign(n, INF);
fr.resize(n);
for(int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
cin >> dir[i].first >> dir[i].second;
dir[i] = {dir[i].first - a[i].first, dir[i].second - a[i].second};
// cout << a[i].first << " " << a[i].second << " ";
// cout << dir[i].first << " " << dir[i].second << "\n";
} cerr << "\n";
vector<pair<int, int>> ps = {
{r, r}, {-r, -r}, {(r-1), (r-1)}, {-(r-1), -(r-1)}
};
for(int i = 0; i < n; i++) {
if (inside(a[i].first, a[i].second)) {
best[i] = 0;
fr[i] = a[i];
continue;
}
for(pair<int, int> j : ps) {
int mov = getP(j.first, a[i].first, dir[i].first);
// cout << a[i].first + mov * dir[i].first << " " << a[i].second + mov * dir[i].second << "\n";
if (mov != -1) {
if (inside(a[i].first + mov * dir[i].first, a[i].second + mov * dir[i].second)) {
if (mov < best[i]) {
best[i] = mov;
fr[i] = {a[i].first + mov * dir[i].first, a[i].second + mov * dir[i].second};
}
}
}
mov = getP(j.second, a[i].second, dir[i].second);
if (mov != -1) {
if (inside(a[i].first + mov * dir[i].first, a[i].second + mov * dir[i].second)) {
if (mov < best[i]) {
best[i] = mov;
fr[i] = {a[i].first + mov * dir[i].first, a[i].second + mov * dir[i].second};
}
}
}
}
}
for(int i = 0; i < n; i++) {
int L = best[i], R = INF, ans = INF;
while(L <= R) {
int mid = (L + R) / 2;
if (dir[i].first != 0 && mid >= abs(INF / dir[i].first)) {
R = mid - 1;
ans = mid;
continue;
}
if (dir[i].second != 0 && mid >= abs(INF / dir[i].second)) {
R = mid - 1;
ans = mid;
continue;
}
if (inside(a[i].first + mid * dir[i].first, a[i].second + mid * dir[i].second)) {
L = mid + 1;
} else {
R = mid - 1;
ans = mid;
}
}
// cerr << best[i] << " " << ans << "\n";
mp[best[i]]++;
mp[ans]--;
}
int ans = 0, curr = 0;
for(auto i : mp) {
if (i.first >= INF) break;
curr += i.second;
ans = max(ans, curr);
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
