#include #include #include #include #include #include #include #include #include #include using namespace std; template istream& operator >> (istream& is, vector& vec){ for(T& c: vec) is >> c; return is; } template ostream& operator << (ostream& os, vector& vec){ for(int i=0; i ostream& operator << (ostream& os, deque& vec){ for(int i=0; i& t, vector& d){ vector ans(n,-1); long long last = 0; long long t_sum = 0; for(int i=0; i=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& t, vector& d){ deque ans(n); iota(ans.begin(), ans.end(), 0); function&)> marge_sorting = [&](deque& dq){ int len = dq.size(); if(len<=1) return; deque a(dq.begin(), dq.begin()+len/2); deque b(dq.begin()+len/2, dq.end()); marge_sorting(a); marge_sorting(b); long long t_sum = 0; deque 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& t, vector& d){ vector 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 t(n),d(n); cin >> t >> d; /* vector ord(n); iota(ord.begin(), ord.end(), 0); long long mx = 0; vector 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; }