| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 456200 |
2021-08-06T08:52:50 Z |
grt |
Zvijezda (COCI19_zvijezda) |
C++17 |
|
125 ms |
8008 KB |
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
struct Point {
ll x, y;
};
const int nax = 1e5 + 10;
int t, n, q;
Point p[nax];
__int128 det(Point a, Point b, Point c) {
return (__int128)(b.x - a.x) * (c.y - a.y) - (__int128)(c.x - a.x) * (b.y - a.y);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t >> n;
for(int i = 0; i < n; ++i) {
cin >> p[i].x >> p[i].y;
}
int cnt = 0;
cin >> q;
while(q--) {
ll a, b;
cin >> a >> b;
a ^= (ll)cnt * cnt * cnt * t;
b ^= (ll)cnt * cnt * cnt * t;
bool sign = det(p[0], p[1], {a, b}) >= 0;
bool sign2 = det(p[n/2], p[n/2 + 1], {a, b}) >= 0;
if(sign && sign2) {
cnt++;
cout << "DA\n";
continue;
}
int r = 0;
int low = 0, high = n/2, mid;
while(low <= high) {
mid = (low + high) / 2;
if((det(p[mid], p[(mid + 1) % n], {a, b}) >= 0) == sign) {
low = mid + 1;
} else {
high = mid - 1;
}
}
r = low - 1;
low = n/2; high = n - 1;
while(low <= high) {
mid = (low + high) / 2;
if((det(p[mid], p[(mid + 1) % n], {a, b}) >= 0) != sign) {
low = mid + 1;
} else {
high = mid - 1;
}
}
int l = low;
//for(int i = n - 1; i >= 1; --i) {
//if((det(p[i], p[(i + 1) % n], {a, b}) >= 0) == sign) {
//l = i;
//} else {
//break;
//}
//}
bool w = false;
if(r == n - 1) {
if(sign) w = true;
} else {
if(sign) {
if(((n - l) % n) + r + 1 > n / 2) w = true;
} else {
if(((n - l) % n) + r + 1 < n / 2) w = true;
}
}
cnt += w;
if(w) cout << "DA\n";
else cout << "NE\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
204 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
3 ms |
332 KB |
Output is correct |
| 9 |
Correct |
2 ms |
332 KB |
Output is correct |
| 10 |
Correct |
3 ms |
332 KB |
Output is correct |
| 11 |
Correct |
2 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
204 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
3 ms |
332 KB |
Output is correct |
| 9 |
Correct |
2 ms |
332 KB |
Output is correct |
| 10 |
Correct |
3 ms |
332 KB |
Output is correct |
| 11 |
Correct |
2 ms |
332 KB |
Output is correct |
| 12 |
Correct |
60 ms |
552 KB |
Output is correct |
| 13 |
Correct |
70 ms |
628 KB |
Output is correct |
| 14 |
Correct |
87 ms |
3140 KB |
Output is correct |
| 15 |
Correct |
95 ms |
5056 KB |
Output is correct |
| 16 |
Correct |
118 ms |
7440 KB |
Output is correct |
| 17 |
Correct |
119 ms |
7416 KB |
Output is correct |
| 18 |
Correct |
77 ms |
4560 KB |
Output is correct |
| 19 |
Correct |
92 ms |
5208 KB |
Output is correct |
| 20 |
Correct |
106 ms |
6132 KB |
Output is correct |
| 21 |
Correct |
116 ms |
7364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
2052 KB |
Output is correct |
| 2 |
Correct |
121 ms |
7956 KB |
Output is correct |
| 3 |
Correct |
98 ms |
5208 KB |
Output is correct |
| 4 |
Correct |
125 ms |
8008 KB |
Output is correct |
| 5 |
Correct |
125 ms |
7876 KB |
Output is correct |
| 6 |
Correct |
119 ms |
7660 KB |
Output is correct |
| 7 |
Correct |
117 ms |
7384 KB |
Output is correct |
| 8 |
Correct |
120 ms |
7956 KB |
Output is correct |
| 9 |
Correct |
115 ms |
7188 KB |
Output is correct |
