fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <numeric>
  5. #include <cassert>
  6.  
  7. using namespace std;
  8.  
  9. constexpr int MAX_M = 10'000;
  10. std::array<int, MAX_M> cnt;
  11.  
  12. long long nchoose2(int n){
  13.   return 1LL * n * (n - 1) / 2;
  14. }
  15.  
  16. long long nchoose3(int n){
  17.   return 1LL * n * (n - 1) * (n - 2) / 6;
  18. }
  19.  
  20. int main(){
  21.   ios_base::sync_with_stdio(false);
  22.  
  23.   int N, M;
  24.   assert(cin >> N >> M);
  25.   assert(1 <= N && N <= 200'000);
  26.   assert(1 <= M && M <= 10'000);
  27.  
  28.   for (int i = 0; i < N; i++){
  29.     int x;
  30.     assert(cin >> x);
  31.     assert(0 <= x && x <= 2'000'000'000);
  32.     cnt[x % M]++;
  33.   }
  34.  
  35.   long long answer = 0;
  36.  
  37.   for (int i = 0; i < M; i++){
  38.     if (cnt[i] > 0){
  39.       for (int j = i; j < M; j++){
  40.         if (cnt[j] > 0){
  41.           int sum = (i + j) % M;
  42.           int k = (M - sum + M) % M;
  43.  
  44.           if (i <= j && j <= k){
  45.             if (i == j && j == k){
  46.               answer += nchoose3(cnt[i]);
  47.             }
  48.             else if (i == j){
  49.               answer += nchoose2(cnt[i]) * cnt[k];
  50.             }
  51.             else if (j == k){
  52.               answer += nchoose2(cnt[j]) * cnt[i];
  53.             }
  54.             else{
  55.               answer += 1LL * cnt[i] * cnt[j] * cnt[k];
  56.             }
  57.           }
  58.         }
  59.       }
  60.     }
  61.   }
  62.  
  63.   cout << answer << "\n";
  64.  
  65.   return 0;
  66. }
  67.  
Runtime error #stdin #stdout #stderr 0s 15280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:24: int main(): Assertion `cin >> N >> M' failed.
https://ideone.com/EOasbx
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!