Submission #9545

#TimeUsernameProblemLanguageResultExecution timeMemory
9545maniacUniting (kriii2_U)C++98
1 / 4
48 ms3228 KiB
#include<cstdio> #include<cassert> #include<cstring> #include<map> #include<set> #include<time.h> #include<algorithm> #include<stack> #include<queue> #include<utility> #include<cmath> #include<iostream> #include<string> #include<vector> #include<limits> using namespace std; #define LL long long #define mod 1000000007 LL n,re,cnt; priority_queue <LL> q; map <LL,LL > mp; long long gcd( long long b, long long s ){ return (s!=0) ? gcd( s, b%s ) : b; } void solve(){ scanf("%lld",&n); cnt = 1; for(LL i = 1; i <= n; i++){ LL a ; scanf("%lld",&a); mp[a] ++; q.push(-a); } if( n == 1){ re = 0; cnt = 0; printf("%lld\n%lld\n",re,cnt); return ; } while( !q.empty() ){ LL a,b; a = -q.top(); q.pop(); b = -q.top(); q.pop(); if( a == b){ cnt *= (mp[a]*(mp[a]-1))%mod; cnt %=mod; mp[a]-=2; } else{ cnt *= (mp[a]*mp[b])%mod; cnt%=mod; cnt *= 2; cnt %=mod; mp[a]--; mp[b]--; } re += (a*b); //re%=mod; if( !q.empty() ){ q.push( -(a+b) ); mp[a+b]++; } } printf("%lld\n%lld\n",re,cnt); } int main(){ solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...