oj.uz

Submission #332296

# Submission time Handle Problem Language Result Execution time Memory
332296 2020-12-02T01:32:07 Z 534351 Zvijezda (COCI19_zvijezda) C++17
110 / 110
 129 ms 8172 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

using namespace std;
// using namespace __gnu_pbds;

// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 100013;

int T, N, Q;
ll C;
pll coor[MAXN];

int ccw(pll a, pll b, pll c)
{
	a.fi -= b.fi; a.se -= b.se;
	c.fi -= b.fi; c.se -= b.se;
    __int128_t cp = (__int128_t) a.fi * c.se - (__int128_t) a.se * c.fi;
    if (cp > 0) return 1;
    if (cp < 0) return -1;
    return 0;
    //idk if this casts properly check it out
}
pll p;

bool ask(int i)
{
    return ccw(p, coor[i], coor[i + 1]) <= 0;
}

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> T >> N;
    FOR(i, 0, N)
    {
        cin >> coor[i].fi >> coor[i].se;
    }
    coor[N] = coor[0];
    cin >> Q;
    while(Q--)
    {
        cin >> p.fi >> p.se;
        if (T)
        {
            p.fi ^= (C * C * C);
            p.se ^= (C * C * C);
        }
        // FOR(i, 0, N)
        // {
        //     cerr << ask(i) << ' ';
        // }
        // cerr << endl;
        //ask (0, n/2). if you get two 1's, you win. if you get two 0's you lose.
        //otherwise you get 01. then you binary search.
        bool lt = ask(0), rt = ask(N/2), ans;
        if (lt == rt)
        {
            ans = lt;
        }
        else
        {
            int lpos, rpos;
            int lo = 0, hi = N/2 - 1;
            while(hi > lo)
            {
                int mid = (hi + lo + 1) >> 1;
                if (ask(mid) == lt) lo = mid;
                else hi = mid - 1;
            }
            lpos = lo; //hi is the last one that's = lo.
            lo = N/2; hi = N - 1;
            while(hi > lo)
            {
                int mid = (hi + lo + 1) >> 1;
                if (ask(mid) == rt) lo = mid;
                else hi = mid - 1;
            }
            rpos = lo;
            //so lpos+1....rpos are rt.
            int c = rpos - lpos;
            ans = (c < N / 2 && !rt) || (c > N / 2 && rt);
        }
        cout << (ans ? "DA" : "NE") << '\n';
        if (ans) C++;
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 3 ms 492 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 3 ms 492 KB Output is correct
11 Correct 3 ms 492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 3 ms 492 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 3 ms 492 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 61 ms 4460 KB Output is correct
13 Correct 78 ms 4588 KB Output is correct
14 Correct 86 ms 4844 KB Output is correct
15 Correct 93 ms 5356 KB Output is correct
16 Correct 119 ms 7532 KB Output is correct
17 Correct 117 ms 7532 KB Output is correct
18 Correct 74 ms 4588 KB Output is correct
19 Correct 94 ms 5296 KB Output is correct
20 Correct 116 ms 6252 KB Output is correct
21 Correct 115 ms 7404 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 2156 KB Output is correct
2 Correct 129 ms 8172 KB Output is correct
3 Correct 95 ms 5356 KB Output is correct
4 Correct 122 ms 8044 KB Output is correct
5 Correct 124 ms 8044 KB Output is correct
6 Correct 119 ms 7660 KB Output is correct
7 Correct 116 ms 7532 KB Output is correct
8 Correct 122 ms 8044 KB Output is correct
9 Correct 115 ms 7276 KB Output is correct