#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; }