Submission #743609

#TimeUsernameProblemLanguageResultExecution timeMemory
743609onebit1024Hexagonal Territory (APIO21_hexagon)C++17
9 / 100
1 ms288 KiB
#include "hexagon.h" #define ll long long #include <vector> ll mod = 1e9+7; ll ma(ll a, ll b){ return (a+b)%mod; } ll mm(ll a, ll b){ return (a*b)%mod; } ll gcdExtended(ll a, ll b, ll *x, ll *y); // Function to find modulo inverse of b. It returns // -1 when inverse doesn't ll modInverse(ll b, ll m) { ll x, y; // used in extended GCD algorithm ll g = gcdExtended(b, m, &x, &y); // Return -1 if b and m are not co-prime if (g != 1) return -1; // m is added to handle negative x return (x%m + m) % m; } // Function to compute a/b under modulo m ll modDivide(ll a, ll b, ll m) { a = a % m; ll inv = modInverse(b, m); return (inv * a) % m; } // C function for extended Euclidean Algorithm (used to // find modular inverse. ll gcdExtended(ll a, ll b, ll *x, ll *y) { // Base Case if (a == 0) { *x = 0, *y = 1; return b; } ll x1, y1; // To store results of recursive call ll gcd = gcdExtended(b%a, a, &x1, &y1); // Update x and y using results of recursive // call *x = y1 - (b/a) * x1; *y = x1; return gcd; } int draw_territory(int N, int A, int B, std::vector<int> D, std::vector<int> L) { ll k = L[0]-2; if(L[0]==1){ return ma(mm(A,3),mm(B,2)); } if(L[0]==2){ return ma(mm(A,6),mm(B,8))%mod; } ll fr = mm(L[0],3),sr=0; if(k%2)sr = mm((k+1)/2,k); else sr = mm(k/2,k+1); int n = L[0]+2; ll val = mm(n,mm(n-1,n-2)); val = modDivide(val,6,mod); val = mm(val,2); return ma(mm(B,val),mm(A,ma(sr,fr))); }
#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...