Submission #332296

#	Time	Username	Problem	Language	Result	Execution time	Memory
332296		534351	Zvijezda (COCI19_zvijezda)	C++17	110 / 110	129 ms	8172 KiB

zvijezda

#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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60