oj.uz

답안 #319042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319042 2020-11-03T19:07:33 Z fivefourthreeone Dragon 2 (JOI17_dragon2) C++17
15 / 100
 4000 ms 1824 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 = 10;
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 38 ms 1260 KB Output is correct
2 Correct 66 ms 1380 KB Output is correct
3 Correct 43 ms 1260 KB Output is correct
4 Correct 49 ms 1764 KB Output is correct
5 Correct 40 ms 1764 KB Output is correct
6 Correct 3 ms 1260 KB Output is correct
7 Correct 3 ms 1260 KB Output is correct
8 Correct 24 ms 1260 KB Output is correct
9 Correct 23 ms 1132 KB Output is correct
10 Correct 24 ms 1132 KB Output is correct

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 1260 KB Output is correct
2 Correct 66 ms 1380 KB Output is correct
3 Correct 43 ms 1260 KB Output is correct
4 Correct 49 ms 1764 KB Output is correct
5 Correct 40 ms 1764 KB Output is correct
6 Correct 3 ms 1260 KB Output is correct
7 Correct 3 ms 1260 KB Output is correct
8 Correct 24 ms 1260 KB Output is correct
9 Correct 23 ms 1132 KB Output is correct
10 Correct 24 ms 1132 KB Output is correct
11 Correct 3497 ms 1824 KB Output is correct
12 Execution timed out 4077 ms 1772 KB Time limit exceeded
13 Halted 0 ms 0 KB -