oj.uz

답안 #319043

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319043 2020-11-03T19:08:02 Z fivefourthreeone Dragon 2 (JOI17_dragon2) C++17
60 / 100
 4000 ms 3300 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 = 0;
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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
dragon2.cpp:102:19: warning: array subscript 0 is above array bounds of 'int [0]' [-Warray-bounds]
  102 |             printf("%d \n", ans[bck[a]][bck[b]]);
      |             ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1132 KB Output is correct
2 Correct 38 ms 1132 KB Output is correct
3 Correct 43 ms 1132 KB Output is correct
4 Correct 49 ms 1508 KB Output is correct
5 Correct 40 ms 1508 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 3 ms 1132 KB Output is correct
8 Correct 14 ms 1132 KB Output is correct
9 Correct 14 ms 1132 KB Output is correct
10 Correct 14 ms 1132 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1824 ms 1824 KB Output is correct
2 Correct 3614 ms 1892 KB Output is correct
3 Correct 96 ms 2788 KB Output is correct
4 Correct 16 ms 2668 KB Output is correct
5 Correct 18 ms 2924 KB Output is correct
6 Correct 1789 ms 2528 KB Output is correct
7 Correct 1776 ms 2528 KB Output is correct
8 Correct 1187 ms 2528 KB Output is correct
9 Correct 1201 ms 2160 KB Output is correct
10 Correct 1193 ms 2400 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1132 KB Output is correct
2 Correct 38 ms 1132 KB Output is correct
3 Correct 43 ms 1132 KB Output is correct
4 Correct 49 ms 1508 KB Output is correct
5 Correct 40 ms 1508 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 3 ms 1132 KB Output is correct
8 Correct 14 ms 1132 KB Output is correct
9 Correct 14 ms 1132 KB Output is correct
10 Correct 14 ms 1132 KB Output is correct
11 Correct 1824 ms 1824 KB Output is correct
12 Correct 3614 ms 1892 KB Output is correct
13 Correct 96 ms 2788 KB Output is correct
14 Correct 16 ms 2668 KB Output is correct
15 Correct 18 ms 2924 KB Output is correct
16 Correct 1789 ms 2528 KB Output is correct
17 Correct 1776 ms 2528 KB Output is correct
18 Correct 1187 ms 2528 KB Output is correct
19 Correct 1201 ms 2160 KB Output is correct
20 Correct 1193 ms 2400 KB Output is correct
21 Correct 1823 ms 2536 KB Output is correct
22 Correct 3614 ms 2560 KB Output is correct
23 Execution timed out 4006 ms 3300 KB Time limit exceeded
24 Halted 0 ms 0 KB -