oj.uz

답안 #485376

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
485376 2021-11-07T12:45:05 Z LptN21 Zvijezda (COCI19_zvijezda) C++14
110 / 110
 151 ms 9520 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define PI acos(-1.0)
#define FF first
#define SS second
#define eps 1e-3
// vector
#define pb push_back
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define lb lower_bound
#define ub upper_bound
// bit
#define CNTBIT(x) __builtin_popcount(x)
#define ODDBIT(x) __builtin_parity(x)
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SUBSET(big, small) (((big)&(small))==(small))
#define MINBIT(x) (x)&(-x)
// typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef __int128 i128;
typedef pair<i128, i128> ii;
typedef pair<int, ii> i3;
/* CODE BELOW */
const int N=1e5+7, M=18+1;
const int MOD=1e9+7;
const int oo=1e9+7;

int n, m, k, t;

ii a[N];

/*bool ccw(ii a, ii b, ii c){
	i128 dx1 = b.first - a.first;
	i128 dy1 = b.second - a.second;
	i128 dx2 = c.first - a.first;
	i128 dy2 = c.second - a.second;
	return dx1 * dy2 - dy1 * dx2<0;
}*/

bool ccw(const ii &a,
         const ii &b,
         const ii &c) {
    i128 d1=a.FF*(c.SS-b.SS);
    i128 d2=b.FF*(a.SS-c.SS);
    i128 d3=c.FF*(b.SS-a.SS);
    return d1+d2+d3>0;
}

int BSu(int l, int r, ii p) {
    int mid, ans=l-1;
    while(l<=r) {
        mid=(l+r)/2;
        if(ccw(p, a[mid%n+1], a[mid])) {
            l=mid+1, ans=mid;
        } else r=mid-1;
    }
    return ans;
}
int BSd(int l, int r, ii p) {
    int mid, ans=r+1;
    while(l<=r) {
        mid=(l+r)/2;
        if(ccw(p, a[mid%n+1], a[mid])) {
            r=mid-1, ans=mid;
        } else l=mid+1;
    }
    return ans;
}

bool qry(ii p) {
    bool sl=ccw(p, a[2], a[1]);
    bool sr=ccw(p, a[n/2+2], a[n/2+1]);
    if(sl&&sr) return 1;
    if(sl^sr) {
        if(sl) { // will be of the kind 1 (n) 1 (1) 1 (2) ... 0 (n/2+1) 0 (n/2+2) ...
            int ans=BSu(1, n/2, p);
            int _ans=BSd(n/2+2, n, p);

            return ans+(n-_ans+1)>n/2;
        } else { // // will be of the kind 0 (n) 0 (1) 0 (2) ... 1 (n/2+1) 1 (n/2+2) ...
            int ans=BSd(1, n/2, p);
            int _ans=BSu(n/2+2, n, p);

            return _ans-ans+1>n/2;
        }
    }
    return 0;
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d%d", &t, &n);
    ll x, y;
    for(int i=1;i<=n;i++) {
        scanf("%lld%lld", &x, &y);
        a[i]=ii(x, y);
    }

    #define sqr3(x) 1LL*(x)*(x)*(x)
    scanf("%d", &m);
    ll cntAns=0;
    for(int i=1;i<=m;i++) {
        ii p; scanf("%lld%lld", &x, &y);
        p.FF = x ^ (t * sqr3(cntAns));
        p.SS = y ^ (t * sqr3(cntAns));

        bool ans=qry(p); cntAns+=ans;
        if(ans) printf("DA");
        else printf("NE");
        printf("\n");
    }

    return 0;
}
/* stuff you should look for
    - int overflow, array bounds
    - special/edge cases (n=1?)
    - do smth instead of nothing and stay organized
    - WRITE STUFF DOWN
    - DONT JUST STICK ON ONE APPROACH
*/

Compilation message

zvijezda.cpp: In function 'int main()':
zvijezda.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d%d", &t, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~
zvijezda.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         scanf("%lld%lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
zvijezda.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     scanf("%d", &m);
      |     ~~~~~^~~~~~~~~~
zvijezda.cpp:110:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         ii p; scanf("%lld%lld", &x, &y);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 436 KB Output is correct
6 Correct 2 ms 416 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 424 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 436 KB Output is correct
6 Correct 2 ms 416 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 424 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 61 ms 4420 KB Output is correct
13 Correct 73 ms 4472 KB Output is correct
14 Correct 102 ms 4920 KB Output is correct
15 Correct 100 ms 5388 KB Output is correct
16 Correct 116 ms 8696 KB Output is correct
17 Correct 113 ms 8772 KB Output is correct
18 Correct 76 ms 4472 KB Output is correct
19 Correct 97 ms 5636 KB Output is correct
20 Correct 109 ms 6876 KB Output is correct
21 Correct 131 ms 8620 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 9196 KB Output is correct
2 Correct 151 ms 9520 KB Output is correct
3 Correct 111 ms 5576 KB Output is correct
4 Correct 116 ms 9392 KB Output is correct
5 Correct 120 ms 9392 KB Output is correct
6 Correct 114 ms 8756 KB Output is correct
7 Correct 135 ms 8808 KB Output is correct
8 Correct 128 ms 9476 KB Output is correct
9 Correct 111 ms 8448 KB Output is correct