fork download
copy 
  1. #pragma GCC optimize ("-O3")
  2. #include <bits/stdc++.h>
  3. // #include <ext/pb_ds/assoc_container.hpp>
  4. // #include <ext/pb_ds/tree_policy.hpp>
  5. // using namespace __gnu_pbds;
  6. //#include <boost/multiprecision/cpp_int.hpp>
  7. //using namespace boost::multiprecision;
  8. using namespace std;
  9.  
  10. #define all(c) (c).begin(),(c).end()
  11. #define endl "\n"
  12. #define ff first
  13. #define ss second
  14. #define allr(c) (c).rbegin(),(c).rend()
  15. #define ifr(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
  16. #define pof pop_front
  17. #define pob pop_back
  18. #define pb emplace_back
  19. #define pf emplace_front
  20. #define fstm(m,n,r) m.reserve(n);m.max_load_factor(r)
  21. #define mp make_pair
  22. #define mt make_tuple
  23. #define inf LLONG_MAX
  24. #define os tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  25. //order_of_key (k) : Number of items strictly smaller than k .
  26. //find_by_order(k) : K-th element in a set (counting from zero).
  27. const double PI = acos(-1);
  28. typedef complex<double> cd;
  29. typedef long long ll;
  30. ll gcd(){return 0ll;} template<typename T,typename... Args> T gcd(T a,Args... args) { return __gcd(a,(__typeof(a))gcd(args...)); }
  31. typedef map<ll,ll> mll;
  32. typedef map<string,ll> msll;
  33. typedef unordered_map<ll,ll> umap;
  34. typedef vector<ll> vll;
  35. typedef pair<ll,ll> pll;
  36. typedef long double ld;
  37. #define mod 1000000007 
  38. #define N 100001
  39.  
  40. int main() {
  41.     ios_base::sync_with_stdio(false);
  42.     cin.tie(NULL);
  43.     cout.tie(NULL);
  44.     #ifndef ONLINE_JUDGE
  45.         freopen("input.txt","r",stdin);
  46.     #endif
  47.     // int T;cin>>T;while(T--) 
  48.     {
  49.         ll n, k, t;
  50.         cin>>n>>k;
  51.         vll pos, neg; ll zero = 0;
  52.         ifr(i, 0, n)  {
  53.             cin>>t;
  54.             if(t==0) zero++;
  55.             else if(t<0) neg.pb(t);
  56.             else pos.pb(t);
  57.         }
  58.         ll ps = pos.size(), ns = neg.size();
  59.         if(k > (ps + ns)) {
  60.             cout<<"0\n";
  61.             return 0;
  62.         }
  63.  
  64.         ll ans = 1;
  65.         if( k == (ps + ns)) {
  66.             // if((ns&1) && zero>0) {
  67.             //     cout<<"0\n";
  68.             //     return 0;
  69.             // }
  70.             ifr(i, 0, ps) ans = (ans*pos[i])%mod;
  71.             ifr(i, 0, ns) ans = (ans*neg[i])%mod;
  72.             ans = (ans + mod)%mod;
  73.             cout<<ans<<endl;
  74.             return 0;
  75.         }
  76.  
  77.         sort(all(pos), greater<ll>());
  78.         sort(all(neg));
  79.  
  80.         if(ns == 0) {
  81.             ans = 1;
  82.             ifr(i, 0, k) ans = (ans*pos[i])%mod;
  83.             cout<<ans<<endl;
  84.             return 0;
  85.         }
  86.  
  87.  
  88.         if(ps == 0) {
  89.             if(k&1) reverse(all(neg));
  90.             if((k&1) && zero>0) {
  91.                 cout<<"0\n";
  92.                 return 0;
  93.             }
  94.             ans = 1;
  95.             ifr(i, 0, k) ans = (ans*neg[i])%mod;
  96.             ans = (ans + mod)%mod;
  97.             cout<<ans<<endl;
  98.             return 0;
  99.         }
  100.  
  101.         vector<ld> pre;
  102.  
  103.         pre.pb(0);
  104.         ifr(i, 0, ps) pre.pb(pre.back() + log(pos[i]));
  105.  
  106.         ld lg = 0, sum, msum = 0; 
  107.         int x=-1, y=-1;
  108.  
  109.         for(int i=0; i<=ns; i++) {
  110.  
  111.             if(k-i<0 ) break;
  112.  
  113.             if(((k-i)>ps) || (i&1)) {
  114.                 lg += log(-neg[i]);
  115.                 continue;
  116.             }
  117.  
  118.             sum = lg + pre[k-i];
  119.  
  120.             // cout<<sum<<" "<<msum<<endl;
  121.  
  122.             if(msum < sum) {
  123.                 msum = sum;
  124.                 x = i; y = k-i;
  125.             }
  126.  
  127.             if(i!=ns) lg += log(-neg[i]);
  128.         }
  129.  
  130.         // cout<<x<<" "<<y<<endl;
  131.         if(x==-1) {
  132.             cout<<0<<endl;
  133.             return 0;
  134.         }
  135.  
  136.         ans = 1;
  137.         if((x&1) && zero>0 ) {
  138.             cout<<"0\n";
  139.             return 0;
  140.         }
  141.         ifr(i, 0, x) ans = (1ll*ans*neg[i])%mod;
  142.         ifr(i, 0, y) ans = (1ll*ans*pos[i])%mod;
  143.         ans = (ans + mod)%mod;
  144.         cout<<ans<<endl;
  145.     }
  146.     return 0;
  147. }
  148.  
Success #stdin #stdout 0s 4552KB
comments (?)
stdin
copy 
5 4
1 2 3 -1 0
stdout
copy 
1000000001
https://ideone.com/QtM9OE
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!