結果

問題 No.14 最小公倍数ソート
コンテスト
ユーザー lunnear
提出日時 2019-10-23 12:12:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,639 bytes
コンパイル時間 759 ms
コンパイル使用メモリ 78,820 KB
実行使用メモリ 12,448 KB
最終ジャッジ日時 2024-07-06 05:09:08
合計ジャッジ時間 7,333 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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