oj.uz

답안 #319041

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319041 2020-11-03T19:06:55 Z fivefourthreeone Dragon 2 (JOI17_dragon2) C++17
15 / 100
 4000 ms 2148 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(auto i=(a);i<(b); ++i)
#define uwu(i,a, b) for(auto i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
 
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = atan(1);
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 30001;
const int magic = 50;
struct pt {
    ll x, y;
    pt(ll x = 0, ll y = 0) : x(x), y(y) {}
    bool operator < (const pt &o) const {
        return (x == o.x ? y < o.y : x < o.x);
    }
    pt operator - (const pt &o) const {
        return pt(x - o.x, y - o.y);
    }
};
ll cross(pt a, pt b) {
    return a.x * b.y - a.y * b.x;
}
bool ccw(pt &a, pt &b, pt &c) {
    return cross(a-b, c-b) <= 0;
}
vector<pt> tribe[mxN];
int ord[mxN];
int bck[mxN];
int ans[magic][magic];
bool ma[mxN];
int n, m, q;
pt x, y;
bool chk(pt &a, pt &b) {
    if(ccw(a, x, y)) {
        if(ccw(a, x, b) && ccw(b, y, a))return 1;
    }else {
        if(ccw(b, x, a) && ccw(a, y, b))return 1;
    }
    return 0;
}
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    scanf("%d %d\n", &n, &m);
    int a, b, c;
    owo(i, 0, n) {
        scanf("%d %d %d\n", &a, &b, &c);
        c--;
        tribe[c].senpai({a, b});
    }
    iota(ord, ord+m, 0);
    sort(ord, ord+m, [&](int o1, int o2) {
        return tribe[o1].size() > tribe[o2].size();
    });
    scanf("%lld %lld %lld %lld\n", &x.x, &x.y, &y.x, &y.y);
    owo(i, 0, m) {
        bck[ord[i]] = i;
        if(i < magic) {
            ma[i] = true;
        }
    }
    owo(i, 0, min(m, magic)) {
        owo(j, 0, min(m, magic)) {
            if(i==j)continue;
            int t1 = ord[i];
            int t2 = ord[j];
            for(auto &k1: tribe[t1]) {
                for(auto &k2: tribe[t2]) {
                    ans[i][j]+=chk(k1, k2);
                    /*if (ccw(k1, x, y)) ans[i][j] += (ccw(k1, x, k2) && ccw(k2, y, k1));
			        else ans[i][j] += (ccw(k2, x, k1) && ccw(k1, y, k2));*/
                }
            }
        }
    }
    scanf("%d\n", &q);
    while(q--) {
        scanf("%d %d\n", &a, &b);
        a--; b--;
        if(ma[bck[a]] && ma[bck[b]]) {
            printf("%d \n", ans[bck[a]][bck[b]]);
        }else {
            int res = 0;
            for(auto &k1: tribe[a]) {
                for(auto &k2: tribe[b]) {
                    res+=chk(k1, k2);
                }
            }
            printf("%d \n", res);
        }
    }
    return 0;
}

Compilation message

dragon2.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
dragon2.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
dragon2.cpp: In function 'int main()':
dragon2.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |     scanf("%d %d\n", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
dragon2.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |         scanf("%d %d %d\n", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |     scanf("%lld %lld %lld %lld\n", &x.x, &x.y, &y.x, &y.y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |     scanf("%d\n", &q);
      |     ~~~~~^~~~~~~~~~~~
dragon2.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |         scanf("%d %d\n", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 1280 KB Output is correct
2 Correct 65 ms 1152 KB Output is correct
3 Correct 53 ms 1132 KB Output is correct
4 Correct 48 ms 1508 KB Output is correct
5 Correct 41 ms 1636 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 3 ms 1132 KB Output is correct
8 Correct 24 ms 1132 KB Output is correct
9 Correct 24 ms 1144 KB Output is correct
10 Correct 24 ms 1260 KB Output is correct

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3497 ms 1952 KB Output is correct
2 Execution timed out 4081 ms 2148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 1280 KB Output is correct
2 Correct 65 ms 1152 KB Output is correct
3 Correct 53 ms 1132 KB Output is correct
4 Correct 48 ms 1508 KB Output is correct
5 Correct 41 ms 1636 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 3 ms 1132 KB Output is correct
8 Correct 24 ms 1132 KB Output is correct
9 Correct 24 ms 1144 KB Output is correct
10 Correct 24 ms 1260 KB Output is correct
11 Correct 3497 ms 1952 KB Output is correct
12 Execution timed out 4081 ms 2148 KB Time limit exceeded
13 Halted 0 ms 0 KB -