任意の入力に対して長方形の面積の最大値を求めるプログラム

Question

Atcoder Beginner Contest071 C問題より、問題文は以下の通りです

問題文

太さが無視できる棒が N 本あります． i 番目の棒の長さは Ai です．

すぬけ君は，これらの棒から 4 本の異なる棒を選び，それらの棒を辺として長方形（正方形を含む）を作りたいです． 作ることができる最大の長方形の面積を求めてください．
制約
4≤N≤10^5
1≤Ai≤10^9
Ai は整数
http://abc071.contest.atcoder.jp/tasks/arc081_a

此方の問題を以下のプログラムで解いたところ、半分以上不正解となりましたが、理由が分かりません

   #include<iostream>
    #include<stdlib.h>
    using namespace std;
     
    int compar(const int *val1, const int *val2);
     
    int main(){
    	int N,i,x=0,y=0;
    	cin>>N;
    	int A[N];
    	for(i=0;i<N;i++){
    		cin>>A[i];
    	}
    	qsort(A,N,sizeof(int),(int (*)(const void *, const void *))compar);

    	for(i=0;i<N-1;i++){
    		if(A[i]==A[i+1]){
    			x=A[i];i+=2;break;
    		}
             }
    	for(;i<N-1;i++){
    		if(A[i]==A[i+1]){
    			y=A[i];break;
    		}
    	}
    	cout<<x*y<<endl;
            return 0;
     
    }
     
     
     
     
     
    int compar(const int *val1, const int *val2) {
        if ( *val1 > *val2 ) {
            return -1;
        } else if ( *val1 == * val2 ) {
            return 0;
        } else {
            return 1;
        }
    }
コード

この問題文は、入力された数のうち、２回以上出現する数字を大きい順に２つ選び出し、その積を求めることと言い換えられます
入力された数字を配列Aに格納し、それをまず降順にソートします
ループ文により、A[i]とA[i+1]が同じであればその値をxに代入し、iに2プラスします
次に、iの値はそのままでyについても同じことをすることで、yに２番目に大きい２回以上出現した数字が代入されます
最後にそれらを掛けて出力して終了です
用意されている入力例で試したところ合ってそうなのですが、全然違うみたいです
どなたか、どこがおかしいか分かる方がいましたらご助力願います
よろしくお願いいたします

Answer 1

例えば入力値が下記の場合はどうなるでしょうか。

4
1000000000 1000000000 1000000000 1000000000

---

追記：

質問に記載のコードについて変数の型を変えただけですが、手元のgcc環境では動作するようでした。

$ g++ -v
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4)
$ cat input
4
1000000000 1000000000 1000000000 1000000000
$ cat input | ./a.out
1000000000000000000

#include <iostream>
#include <stdlib.h>
using namespace std;

int compar(const long long *val1, const long long *val2);

int main(void)
{
    long long N, i, x = 0, y = 0;
    cin >> N;
    long long A[N];

    for (i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    qsort(A, N, sizeof(long long), (int (*)(const void *, const void *))compar);

    for (i = 0; i < N-1; i++)
    {
        if (A[i] == A[i+1])
        {
            x = A[i];
            i += 2;
            break;
        }
    }

    for (; i < N-1; i++)
    {
        if (A[i] == A[i+1])
        {
            y = A[i];
            break;
        }
    }

    cout << x * y << endl;

    return 0;
}

int compar(const long long *val1, const long long *val2)
{
    if (*val1 > *val2)
    {
        return -1;
    }
    else if (*val1 == *val2)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}

Comments

[l_h_l_h]

回答ありがとうございます
試したところ、25と出力されました

[退会済みユーザー]

すみません、コードを読み違えていたので条件を変更しました。

[l_h_l_h]

ありがとうございます
謎の大きな負の数が出力されてしまいました
long型で試してみてもダメだったのですが、どこがおかしいでしょうか？（それどころか、long型にしたら出力結果が全部0になってしまいました……)

[退会済みユーザー]

xとyの積がintの範囲を超えるため、算術オーバーフローが発生しています。
これをどのように回避するのか、というのがこの設問での課題です。

[退会済みユーザー]

きちんと正攻法で解かれるようであれば、困難は分割せよ、というところでしょうか。
具体的な話まですると、多倍長整数で調べられるとよいでしょう。

とにかく解ければ、ということであれば、使えるものは使え、ということになるかと思います。
long intがダメだったというのは処理系にもよるので一概には理由は言えませんが、言語仕様上long long intというものもあります。

[l_h_l_h]

ありがとうございます
long long int、mp::cpp_intの両方を試してみましたが、出力はいずれも0となってしまいました
大きい数の分割にはどのような手法があるでしょうか？

[退会済みユーザー]

> 大きい数の分割にはどのような手法があるでしょうか？
一番イメージしやすい形は、筆算での計算方法です。
筆算では、1桁同士の計算と繰り上がりを用いて、複数桁同士の和や積を求めることを可能としています。
これを変数が扱える範囲で同様に行うことで、任意精度の計算が可能となります。

[l_h_l_h]

変数の型を変えても出力が0になる件ですが、恥ずかしながらクイックソートの引数を変えるのを忘れていました……
無事正解になりました！
筆算の考え方は盲点でした　こちらも試してみようと思います
長々とありがとうございました！