oj.uz

Submission #319037

# Submission time Handle Problem Language Result Execution time Memory
319037 2020-11-03T18:59:17 Z fivefourthreeone Dragon 2 (JOI17_dragon2) C++17
15 / 100
 4000 ms 2016 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);
    cin>>n>>m;
    int a, b, c;
    owo(i, 0, n) {
        cin>>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();
    });
    cin>>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));*/
                }
            }
        }
    }
    cin>>q;
    while(q--) {
        cin>>a>>b;
        a--; b--;
        if(ma[bck[a]] && ma[bck[b]]) {
            cout<<ans[bck[a]][bck[b]]<<"\n";
        }else {
            int res = 0;
            for(auto &k1: tribe[a]) {
                for(auto &k2: tribe[b]) {
                    res+=chk(k1, k2);
                }
            }
            cout<<res<<"\n";
        }
    }
    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")
      |

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1260 KB Output is correct
2 Correct 70 ms 1132 KB Output is correct
3 Correct 54 ms 1260 KB Output is correct
4 Correct 41 ms 1388 KB Output is correct
5 Correct 32 ms 1380 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 3 ms 1132 KB Output is correct
8 Correct 24 ms 1132 KB Output is correct
9 Correct 23 ms 1132 KB Output is correct
10 Correct 24 ms 1260 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3507 ms 1824 KB Output is correct
2 Execution timed out 4059 ms 2016 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1260 KB Output is correct
2 Correct 70 ms 1132 KB Output is correct
3 Correct 54 ms 1260 KB Output is correct
4 Correct 41 ms 1388 KB Output is correct
5 Correct 32 ms 1380 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 3 ms 1132 KB Output is correct
8 Correct 24 ms 1132 KB Output is correct
9 Correct 23 ms 1132 KB Output is correct
10 Correct 24 ms 1260 KB Output is correct
11 Correct 3507 ms 1824 KB Output is correct
12 Execution timed out 4059 ms 2016 KB Time limit exceeded
13 Halted 0 ms 0 KB -