Submission #319041

#TimeUsernameProblemLanguageResultExecution timeMemory
319041fivefourthreeoneDragon 2 (JOI17_dragon2)C++17
15 / 100
4081 ms2148 KiB
#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 (stderr)

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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...