제출 #485631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
485631		Neos	Zvijezda (COCI19_zvijezda)	C++14	110 / 110	123 ms	8004 KiB

zvijezda

#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"));
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60