# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
485631 |
2021-11-08T16:17:17 Z |
Neos |
Zvijezda (COCI19_zvijezda) |
C++14 |
|
123 ms |
8004 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
#define task "test"
#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i, l, r) for( ll i = (l) ; i < (r) ; i++ )
#define forb(i, r, l) for( ll i = (r) ; i >= (l) ; i-- )
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define debug(x) cerr << #x << " = " << x << '\n';
const int N = 1e5 + 7;
int t, n, m, x;
ii a[N], y;
double ccw(ii a, ii b, ii c) {
return (double)a.fi * (b.se - c.se) + (double)b.fi * (c.se - a.se) + (double)c.fi * (a.se - b.se);
}
ll sqr3(int x) {
return 1ll * x * x * x;
}
bool get(int i, ii x) {
return ccw(a[i], a[(i + 1) % n], x) >= 0;
}
int bs(int lo, int hi, ii x) {
int l = lo, r = hi;
while (l <= r) {
int mid = l + r >> 1;
if (get(mid, x) == get(lo, x)) l = mid + 1;
else r = mid - 1;
}
return (!get(lo, x) ? n / 2 - l + lo : l - lo);
}
bool qry(ii x) {
ii res = mp(get(0, x), get(n / 2, x));
if (!(res.fi ^ res.se)) return res.fi;
return bs(0, n / 2 - 1, x) + bs(n / 2, n - 1, x) > n / 2;
}
int main() {
// fastIO;
scanf("%d %d", &t, &n);
forw(i, 0, n) scanf("%lld %lld", &a[i].fi, &a[i].se);
int cnt = 0;
scanf("%d", &m);
while (m--) {
scanf("%lld %lld", &y.fi, &y.se);
ii x = mp(y.fi ^ (t * sqr3(cnt)), y.se ^ (t * sqr3(cnt)));
int ans = qry(x); cnt += ans;
printf((ans ? "DA\n" : "NE\n"));
}
}
Compilation message
zvijezda.cpp: In function 'int bs(int, int, ii)':
zvijezda.cpp:53:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mid = l + r >> 1;
| ~~^~~
zvijezda.cpp: In function 'int main()':
zvijezda.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d %d", &t, &n);
| ~~~~~^~~~~~~~~~~~~~~~~
zvijezda.cpp:69:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | forw(i, 0, n) scanf("%lld %lld", &a[i].fi, &a[i].se);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
zvijezda.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d", &m);
| ~~~~~^~~~~~~~~~
zvijezda.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%lld %lld", &y.fi, &y.se);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
312 KB |
Output is correct |
4 |
Correct |
2 ms |
460 KB |
Output is correct |
5 |
Correct |
2 ms |
396 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
2 ms |
440 KB |
Output is correct |
8 |
Correct |
3 ms |
416 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
312 KB |
Output is correct |
4 |
Correct |
2 ms |
460 KB |
Output is correct |
5 |
Correct |
2 ms |
396 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
2 ms |
440 KB |
Output is correct |
8 |
Correct |
3 ms |
416 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
2 ms |
332 KB |
Output is correct |
12 |
Correct |
58 ms |
4472 KB |
Output is correct |
13 |
Correct |
72 ms |
4332 KB |
Output is correct |
14 |
Correct |
84 ms |
4716 KB |
Output is correct |
15 |
Correct |
92 ms |
4972 KB |
Output is correct |
16 |
Correct |
116 ms |
7488 KB |
Output is correct |
17 |
Correct |
113 ms |
7432 KB |
Output is correct |
18 |
Correct |
72 ms |
4444 KB |
Output is correct |
19 |
Correct |
89 ms |
5188 KB |
Output is correct |
20 |
Correct |
104 ms |
6316 KB |
Output is correct |
21 |
Correct |
113 ms |
7296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
7680 KB |
Output is correct |
2 |
Correct |
123 ms |
7848 KB |
Output is correct |
3 |
Correct |
98 ms |
5144 KB |
Output is correct |
4 |
Correct |
121 ms |
8004 KB |
Output is correct |
5 |
Correct |
119 ms |
7920 KB |
Output is correct |
6 |
Correct |
112 ms |
7376 KB |
Output is correct |
7 |
Correct |
115 ms |
7376 KB |
Output is correct |
8 |
Correct |
117 ms |
7880 KB |
Output is correct |
9 |
Correct |
111 ms |
7184 KB |
Output is correct |