結果

問題 No.322 Geometry Dash
コンテスト
ユーザー koyumeishi
提出日時 2015-12-15 18:46:56
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,318 bytes
コンパイル時間 576 ms
コンパイル使用メモリ 71,856 KB
最終ジャッジ日時 2024-11-14 19:30:54
合計ジャッジ時間 2,490 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘void solve2(int&, std::vector<int>&, std::vector<int>&)’:
main.cpp:78:9: error: ‘iota’ was not declared in this scope
   78 |         iota(ans.begin(), ans.end(), 0);
      |         ^~~~
main.cpp:80:9: error: ‘function’ was not declared in this scope
   80 |         function<void(deque<int>&)> marge_sorting = [&](deque<int>& dq){
      |         ^~~~~~~~
main.cpp:11:1: note: ‘std::function’ is defined in header ‘<functional>’; did you forget to ‘#include <functional>’?
   10 | #include <set>
  +++ |+#include <functional>
   11 | using namespace std;
main.cpp:80:18: error: expected primary-expression before ‘void’
   80 |         function<void(deque<int>&)> marge_sorting = [&](deque<int>& dq){
      |                  ^~~~
main.cpp:131:9: error: ‘marge_sorting’ was not declared in this scope
  131 |         marge_sorting(ans);
      |         ^~~~~~~~~~~~~
main.cpp: In function ‘void solve3(int&, std::vector<int>&, std::vector<int>&)’:
main.cpp:140:9: error: ‘iota’ was not declared in this scope
  140 |         iota(ans.begin(), ans.end(), 0);
      |         ^~~~

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

template<class T>
istream& operator >> (istream& is, vector<T>& vec){
	for(T& c: vec) is >> c;
	return is;
}

template<class T>
ostream& operator << (ostream& os, vector<T>& vec){
	for(int i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"\n":" ");
	return os;
}
template<class T>
ostream& operator << (ostream& os, deque<T>& vec){
	for(int i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"\n":" ");
	return os;
}

//O(n^2)
void solve(int& n, vector<int>& t, vector<int>& d){
	vector<int> ans(n,-1);

	long long last = 0;
	long long t_sum = 0;

	for(int i=0; i<n; i++){
		int pos = i;
		long long val = last + t_sum * d[i];
		long long max_ = val;
		long long delta = 0;
		ans[i] = i;
		for(int j=i-1; j>=0; j--){
			int k = ans[j];
			val = val + d[k]*t[i] - d[i]*t[k];
			
			delta += d[k]*t[i] - d[i]*t[k];

			if(val>max_){
				max_ = val;
				pos = j;
			}

			cerr << delta << " ";
		}
		cerr << endl;
		int j = i;
		while(j!=pos){
			swap(ans[j], ans[j-1]);
			j--;
		}

		last = max_;
		t_sum += t[i];
	}
	for(int k: ans){
		printf("{%d, %d},", t[k], d[k]);
	}
	puts("");
	for(int& v: ans) v++;
	cout << ans << endl;
	cout << last << endl;
}

//O(n log n)
void solve2(int& n, vector<int>& t, vector<int>& d){
	deque<int> ans(n);
	iota(ans.begin(), ans.end(), 0);

	function<void(deque<int>&)> marge_sorting = [&](deque<int>& dq){
		int len = dq.size();
		if(len<=1) return;

		deque<int> a(dq.begin(), dq.begin()+len/2);
		deque<int> b(dq.begin()+len/2, dq.end());

		marge_sorting(a);
		marge_sorting(b);

		long long t_sum = 0;
		deque<int> res;
		{
			int x = a.front();
			int y = b.front();
			if(t[x]*d[y] >= t[y]*d[x]){
				res.push_back(x);
				a.pop_front();
				t_sum += t[x];
			}else{
				res.push_back(y);
				b.pop_front();
				t_sum += t[y];
			}
		}

		while(a.size() || b.size()){
			if(a.size()>0 && b.size()>0){
				int x = a.front();
				int y = b.front();

				if(t[x]*d[y] >= t[y]*d[x]){
					res.push_back(x);
					a.pop_front();
					t_sum += t[x];
				}else{
					res.push_back(y);
					b.pop_front();
					t_sum += t[y];
				}

			}else if(a.size()){
				res.push_back(a.front());
				a.pop_front();
			}else{
				res.push_back(b.front());
				b.pop_front();
			}
		}
		dq = res;
	};
	marge_sorting(ans);

	for(int& v: ans) v++;
	cout << ans;
}

//O(n log n)
void solve3(int& n, vector<int>& t, vector<int>& d){
	vector<int> ans(n);
	iota(ans.begin(), ans.end(), 0);

	auto comp = [&](const int& x, const int& y){
		return t[x]*d[y] >= t[y]*d[x];
	};

	sort(ans.begin(), ans.end(), comp);

	for(int& v: ans) v++;
	cout << ans;

}


int main(){
	int n;
	cin >> n;
	vector<int> t(n),d(n);
	cin >> t >> d;
	/*

	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);

	long long mx = 0;
	vector<int> ans;
	do{
		long long val = 0;
		long long sum = 0;
		for(int k:ord){
			val += sum * d[k];
			sum += t[k];
		}
		if(val>mx){
			mx = val;
			ans = ord;
		}

	}while( next_permutation(ord.begin(), ord.end()) );

	cout << ans << endl;
	for(int k: ans){
		printf("{%d, %d},", t[k], d[k]);
	}
	puts("");

	*/

	//solve(n,t,d);
	solve2(n,t,d);
	//solve3(n,t,d);

	return 0;
}
0