結果
| 問題 | 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言語の場合は開発者のデバッグのため、公開されます。
ただし、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);
| ^~~~
ソースコード
#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;}