Submission #995529

#TimeUsernameProblemLanguageResultExecution timeMemory
995529thelegendary08Hexagonal Territory (APIO21_hexagon)C++14
36 / 100
26 ms8908 KiB
#include "hexagon.h" #include<bits/stdc++.h> #define ll long long int #define f0r(i,n) for(int i = 0;i<n;i++) #define pb push_back using namespace std; const ll mod = 1e9 + 7; ll binexp(ll a, ll b){ ll r = 1; f0r(i, 32){ if(b & (1<<i)){ r *= a; r %= mod; } a *= a; a %= mod; } return r; } void move(ll &x, ll &y, int d, int l){ if(d == 1){ y+=l; } else if(d == 2){ x+=l; y+=l; } else if(d == 3){ x+=l; } else if(d == 4)y-=l; else if(d == 5){ x-=l; y-=l; } else x-=l; } int draw_territory(int N, int A, int B, std::vector<int> D, std::vector<int> L) { if(B == 0){ vector<pair<ll, ll>>polygon; polygon.pb({0,0}); ll boundary = 0; ll x = 0; ll y= 0; f0r(i,N){ boundary += L[i]; boundary %= mod; move(x, y, D[i], L[i]); polygon.pb(make_pair(x,y)); } //polygon.pb({0,0}); ll area = 0; f0r(i,N){ pair<ll,ll>a = polygon[i]; pair<ll,ll>b = polygon[i+1]; area += a.first * b.second - b.first * a.second; } area = abs(area); //area/=2; ll inside = ((area - boundary)/2 + 1) % mod; return (boundary + inside) * A % mod; } else{ ll n = L[0] + 1; ll sz = n * (n + 1)/2; sz %= mod; n--; ll sdist = 0; sdist += n * (n+1) % mod; sdist *= (2*n+1) % mod; sdist %= mod; sdist *= binexp(6, mod-2); sdist %= mod; ll b = n * (n+1) % mod; b *= binexp(2, mod - 2); b %= mod; sdist += b; sdist %= mod; ll ans = (sz * A % mod) + (sdist * B % mod); return ans % mod; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...