oj.uz

Submission #899361

# Submission time Handle Problem Language Result Execution time Memory
899361 2024-01-05T21:24:52 Z votranngocvy Zvijezda (COCI19_zvijezda) C++14
110 / 110
 104 ms 8056 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
const int N = 1e5 + 5;
pii a[N];
int n,x,y;

ld ccw(pii a,pii b,pii c) {
    return (ld)a.fi * (b.se - c.se) + (ld)b.fi * (c.se - a.se) + (ld)c.fi * (a.se - b.se);
}

bool calc(int i) {
    return ccw(a[i],a[(i + 1) % n],mp(x,y)) >= 0;
}

int tknp(int l,int r) {
    int low = l,high = r;
    while (low < high) {
        int mid = (low + high + 1) / 2;
        if (calc(l) == calc(mid)) low = mid;
        else high = mid - 1;
    }
    int ans = low - l + 1;
    if (!calc(l)) return n / 2 - ans;
    return ans;
}

bool solve() {
    int a = calc(0),b = calc(n / 2);
    if (a == b) return a;
    return (tknp(0,n / 2 - 1) + tknp(n / 2,n - 1)) >= (n / 2 + 1);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t >> n;
    for (int i = 0; i < n; i++) cin >> a[i].fi >> a[i].se;
    int q;
    cin >> q;
    int cnt = 0;
    while (q--) {
        cin >> x >> y;
        x ^= t * cnt * cnt * cnt;
        y ^= t * cnt * cnt * cnt;
        int ans = solve();
        cnt += ans;
        if (ans) cout << "DA\n";
        else cout << "NE\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 608 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 608 KB Output is correct
12 Correct 43 ms 4436 KB Output is correct
13 Correct 62 ms 4432 KB Output is correct
14 Correct 75 ms 4692 KB Output is correct
15 Correct 80 ms 5204 KB Output is correct
16 Correct 99 ms 7504 KB Output is correct
17 Correct 102 ms 7576 KB Output is correct
18 Correct 63 ms 4416 KB Output is correct
19 Correct 78 ms 5200 KB Output is correct
20 Correct 92 ms 6212 KB Output is correct
21 Correct 99 ms 7480 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 7928 KB Output is correct
2 Correct 104 ms 8020 KB Output is correct
3 Correct 82 ms 5192 KB Output is correct
4 Correct 103 ms 8056 KB Output is correct
5 Correct 104 ms 8020 KB Output is correct
6 Correct 99 ms 7508 KB Output is correct
7 Correct 101 ms 7508 KB Output is correct
8 Correct 103 ms 7872 KB Output is correct
9 Correct 98 ms 7408 KB Output is correct