oj.uz

Submission #319035

# Submission time Handle Problem Language Result Execution time Memory
319035 2020-11-03T18:58:15 Z fivefourthreeone Dragon 2 (JOI17_dragon2) C++17
15 / 100
 4000 ms 2532 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 = 150;
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 1132 KB Output is correct
2 Correct 65 ms 1260 KB Output is correct
3 Correct 80 ms 1380 KB Output is correct
4 Correct 50 ms 2276 KB Output is correct
5 Correct 35 ms 2412 KB Output is correct
6 Correct 4 ms 1388 KB Output is correct
7 Correct 3 ms 1388 KB Output is correct
8 Correct 24 ms 1260 KB Output is correct
9 Correct 24 ms 1132 KB Output is correct
10 Correct 24 ms 1280 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3511 ms 1948 KB Output is correct
2 Execution timed out 4054 ms 2532 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 1132 KB Output is correct
2 Correct 65 ms 1260 KB Output is correct
3 Correct 80 ms 1380 KB Output is correct
4 Correct 50 ms 2276 KB Output is correct
5 Correct 35 ms 2412 KB Output is correct
6 Correct 4 ms 1388 KB Output is correct
7 Correct 3 ms 1388 KB Output is correct
8 Correct 24 ms 1260 KB Output is correct
9 Correct 24 ms 1132 KB Output is correct
10 Correct 24 ms 1280 KB Output is correct
11 Correct 3511 ms 1948 KB Output is correct
12 Execution timed out 4054 ms 2532 KB Time limit exceeded
13 Halted 0 ms 0 KB -