CCCHK '15 S1 - Finding number of pairs

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 0.1s
Java 0.3s
Python 2 0.3s
Python 3 0.3s
Memory limit: 256M
Problem type

Given a sequence of n integers A[1], A[2], \dots, A[n] and a nonnegative integer M, count the number of pairs (i,j) that satisfy the following two conditions: i<j, and A[i]+A[j] \le M.

Input Specification

  • The first line contains integers n (2 \le n \le 10^5) and M (0 \le M \le 10^9), separated by a space.
  • The second line contains n integers, which denotes A[1], A[2], \dots, A[n] (0 \le A[i] \le 10^9).
  • In 50\% of the test cases, n \le 1000.

Output Specification

  • The output contains an integer, which denotes the number of pairs that satisfy the two conditions.
  • If the output is smaller than 10^9+7, please keep it as is. Otherwise, output the number mod 10^9+7.

Sample Input 1

5 6
1 2 3 4 5

Sample Output 1

6

Sample Input 2

5 12
3 6 8 2 8

Sample Output 2

7

Explanation: In Sample 1, among the pairs, (1,2), (1,3), (1,4), (1,5), (2,3), (2,4) satisfy the conditions. In Sample 2, (1,2), (1,3), (1,4), (1,5), (2,4), (3,4), (4,5) satisfy the conditions.

Comments


  • 4
    JohnstonLiu  commented on Nov. 17, 2020, 8:38 p.m.

    What am I doing wrong for the last test cases? Keep getting WA.


    • 8
      Air  commented on Nov. 17, 2020, 9:19 p.m.

      You are outputting your answers mod 10^{10}+7 instead of by mod 10^9+7. Your code, counter%(10000000000+7), has one extra zero.

      If you want to avoid similar issues in the future, try defining a global variable for your "mod" constant for consistency.

      Such as with int mod = 1e9+7; in C++. So, use counter%mod in that case.


      • 5
        JohnstonLiu  commented on Nov. 18, 2020, 7:36 p.m.

        Thanks! I completely missed that one.


  • -22
    RonldLiu  commented on Nov. 11, 2020, 7:12 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 19
      kevinyang  commented on Nov. 12, 2020, 4:55 p.m. ← edited

      I thought you said you were good enough to qualify for IOI 2022


      • 14
        kdrkdr  commented on Nov. 12, 2020, 5:29 p.m. ← edited

        again, hes just smurfing and pretending to be bad. smh. He's guaranteed ioi 2022 watch.


  • -8
    SagarSaha  commented on June 30, 2020, 10:41 p.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 15
      AlanL  commented on July 2, 2020, 3:34 p.m.

      So solutions like yours can't pass. Find a more efficient way to solve the problem.