結果

問題 No.14 最小公倍数ソート
ユーザー lunnearlunnear
提出日時 2019-10-23 12:12:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,639 bytes
コンパイル時間 770 ms
コンパイル使用メモリ 77,296 KB
実行使用メモリ 9,940 KB
最終ジャッジ日時 2023-09-20 09:32:30
合計ジャッジ時間 7,651 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 349 ms
4,376 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <climits>
#include <utility>
#include <map>

using namespace std;

typedef pair<int, int> pattern;

class GCD
{
private:
	map<pattern, int> memo;
	
public:
	int gcd(pattern *p);
	
private:
	int _gcd(pattern *p);
	void swapPattern(pattern *p);
	
public:
	int operator ()(pattern *p){return gcd(p);}
	int operator ()(int x, int y){pattern p = make_pair(x, y); return gcd(&p);}
};

int GCD::gcd(pattern *p)
{
	if(p->first < p->second)
		swapPattern(p);
	
	return _gcd(p);
}

int GCD::_gcd(pattern *p)
{
	auto f = memo.find((*p));
	if(f != memo.end())
	{
		return (*f).second;
	}
	
	int r = p->first % p->second;
	if(r == 0)
	{
		memo.insert(make_pair((*p), p->second));
		return p->second;
	}
	
	pattern q = make_pair(p->second, r);
	return _gcd(&q);
}

void GCD::swapPattern(pattern *p)
{
	int temp = p->first;
	p->first = p->second;
	p->second = temp;
	
	return;
}
	
int main()
{
	GCD gcd;
	int n;
	
	cin >> n;
	pattern list[n];
	
	for(int i = 0; i < n; i++)
	{
		cin >> list[i].first;
	}
	
	list[0].second = INT_MAX;
	for(int i = 0; i < (n - 1); i++)
	{
		int min = 0;
		for(int j = i + 1; j < n; j++)
		{
			list[j].second = (list[i].first * list[j].first) / gcd(list[i].first, list[j].first);
			if(list[min].second >= list[j].second)
			{
			    if(list[min].second == list[j].second)
			        min = (list[min].first > list[j].first)? j:min;
			    else
			        min = j;
			}
		}
		int temp = list[i + 1].first;
		list[i + 1].first = list[min].first;
		list[min].first = temp;
	}
	
	cout << list[0].first;
	for(int i = 1; i < n; i++)
	{
		cout << " " << list[i].first;
	}
	cout << endl;
	
	return 0;
}
0