QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #257340 | #7750. Revenge on My Boss | ucup-team1134# | WA | 2296ms | 85700kb | C++17 | 8.3kb | 2023-11-19 02:38:19 | 2023-11-19 02:38:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=100005;
const ll INF=1LL<<61;
vector<ll> X[MAX],Y[MAX];
ll A[MAX],B[MAX],C[MAX];
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
int Q;cin>>Q;
while(Q--){
int N;cin>>N;
ll ans=INF;
vector<int> Pans;
for(int i=0;i<N;i++){
ll a,b,c;cin>>a>>b>>c;
A[i]=a;
B[i]=b;
C[i]=c;
X[i]={a,b,c,a+b,a-b,a*c,b*c,(a+b)*c,(a-b)*c,a*b*c,a*b,a*c,b*c,a,b,c,a,b,a+b,a-b,a,a*b};
Y[i]={1,1,1,1,1,1,1,1,1,1,c,b,a,b*c,a*c,a*b,c,c,c,c,b,1};
for(int j=0;j<22;j++) X[i].push_back(-X[i][j]);
for(int j=0;j<22;j++) Y[i].push_back(Y[i][j]);
}
for(int s=0;s<44;s++){
vector<int> id,zero,ba;
for(int i=0;i<N;i++){
if(A[i]<B[i]) id.push_back(i);
else if(A[i]==B[i]) zero.push_back(i);
else ba.push_back(i);
}
{
sort(all(id),[&](int a,int b){
if(X[a][s]*Y[b][s]==X[b][s]*Y[a][s]) return C[a]>C[b];
else return X[a][s]*Y[b][s]<X[b][s]*Y[a][s];
});
sort(all(ba),[&](int a,int b){
if(X[a][s]*Y[b][s]==X[b][s]*Y[a][s]) return C[a]<C[b];
else return X[a][s]*Y[b][s]<X[b][s]*Y[a][s];
});
vector<int> P;
for(int x:id) P.push_back(x);
for(int x:zero) P.push_back(x);
for(int x:ba) P.push_back(x);
vector<ll> Arui(N+1),Brui(N+1);
for(int i=1;i<=N;i++){
Arui[i]=Arui[i-1]+A[P[i-1]];
Brui[i]=Brui[i-1]+B[P[i-1]];
}
ll ma=-INF;
for(int i=1;i<=N;i++){
chmax(ma,(Arui[i]+Brui[N]-Brui[i-1])*C[P[i-1]]);
}
if(chmin(ans,ma)) Pans=P;
}
{
sort(all(id),[&](int a,int b){
if(X[a][s]*Y[b][s]==X[b][s]*Y[a][s]) return C[a]>C[b];
else return X[a][s]*Y[b][s]<X[b][s]*Y[a][s];
});
sort(all(ba),[&](int a,int b){
if(X[a][s]*Y[b][s]==X[b][s]*Y[a][s]) return C[a]<C[b];
else return X[a][s]*Y[b][s]>X[b][s]*Y[a][s];
});
vector<int> P;
for(int x:id) P.push_back(x);
for(int x:zero) P.push_back(x);
for(int x:ba) P.push_back(x);
vector<ll> Arui(N+1),Brui(N+1);
for(int i=1;i<=N;i++){
Arui[i]=Arui[i-1]+A[P[i-1]];
Brui[i]=Brui[i-1]+B[P[i-1]];
}
ll ma=-INF;
for(int i=1;i<=N;i++){
chmax(ma,(Arui[i]+Brui[N]-Brui[i-1])*C[P[i-1]]);
}
if(chmin(ans,ma)) Pans=P;
}
{
vector<int> P(N);iota(all(P),0);
sort(all(P),[&](int a,int b){
return X[a][s]*Y[b][s]<X[b][s]*Y[a][s];
});
vector<ll> Arui(N+1),Brui(N+1);
for(int i=1;i<=N;i++){
Arui[i]=Arui[i-1]+A[P[i-1]];
Brui[i]=Brui[i-1]+B[P[i-1]];
}
ll ma=-INF;
for(int i=1;i<=N;i++){
chmax(ma,(Arui[i]+Brui[N]-Brui[i-1])*C[P[i-1]]);
}
if(chmin(ans,ma)) Pans=P;
}
}
{
vector<int> id,zero,ba;
for(int i=0;i<N;i++){
if(A[i]<B[i]) id.push_back(i);
else if(A[i]==B[i]) zero.push_back(i);
else ba.push_back(i);
}
{
sort(all(id),[&](int a,int b){
return (A[a]+A[b]+B[b])*C[b]<(A[b]+A[a]+B[a])*C[a];
});
sort(all(ba),[&](int a,int b){
return (A[a]+B[a]+B[b])*C[a]<(A[b]+B[b]+B[a])*C[b];
});
vector<int> P;
for(int x:id) P.push_back(x);
for(int x:zero) P.push_back(x);
for(int x:ba) P.push_back(x);
vector<ll> Arui(N+1),Brui(N+1);
for(int i=1;i<=N;i++){
Arui[i]=Arui[i-1]+A[P[i-1]];
Brui[i]=Brui[i-1]+B[P[i-1]];
}
ll ma=-INF;
for(int i=1;i<=N;i++){
chmax(ma,(Arui[i]+Brui[N]-Brui[i-1])*C[P[i-1]]);
}
if(chmin(ans,ma)) Pans=P;
}
{
sort(all(id),[&](int a,int b){
return (A[a]+A[b]+B[b])*C[b]<(A[b]+A[a]+B[a])*C[a];
});
sort(all(ba),[&](int a,int b){
return (A[a]+B[a]+B[b])*C[a]>(A[b]+B[b]+B[a])*C[b];
});
vector<int> P;
for(int x:id) P.push_back(x);
for(int x:zero) P.push_back(x);
for(int x:ba) P.push_back(x);
vector<ll> Arui(N+1),Brui(N+1);
for(int i=1;i<=N;i++){
Arui[i]=Arui[i-1]+A[P[i-1]];
Brui[i]=Brui[i-1]+B[P[i-1]];
}
ll ma=-INF;
for(int i=1;i<=N;i++){
chmax(ma,(Arui[i]+Brui[N]-Brui[i-1])*C[P[i-1]]);
}
if(chmin(ans,ma)) Pans=P;
}
{
sort(all(id),[&](int a,int b){
return (A[a]+A[b]+B[b])*C[b]>(A[b]+A[a]+B[a])*C[a];
});
sort(all(ba),[&](int a,int b){
return (A[a]+B[a]+B[b])*C[a]>(A[b]+B[b]+B[a])*C[b];
});
vector<int> P;
for(int x:id) P.push_back(x);
for(int x:zero) P.push_back(x);
for(int x:ba) P.push_back(x);
vector<ll> Arui(N+1),Brui(N+1);
for(int i=1;i<=N;i++){
Arui[i]=Arui[i-1]+A[P[i-1]];
Brui[i]=Brui[i-1]+B[P[i-1]];
}
ll ma=-INF;
for(int i=1;i<=N;i++){
chmax(ma,(Arui[i]+Brui[N]-Brui[i-1])*C[P[i-1]]);
}
if(chmin(ans,ma)) Pans=P;
}
{
sort(all(id),[&](int a,int b){
return (A[a]+A[b]+B[b])*C[b]>(A[b]+A[a]+B[a])*C[a];
});
sort(all(ba),[&](int a,int b){
return (A[a]+B[a]+B[b])*C[a]<(A[b]+B[b]+B[a])*C[b];
});
vector<int> P;
for(int x:id) P.push_back(x);
for(int x:zero) P.push_back(x);
for(int x:ba) P.push_back(x);
vector<ll> Arui(N+1),Brui(N+1);
for(int i=1;i<=N;i++){
Arui[i]=Arui[i-1]+A[P[i-1]];
Brui[i]=Brui[i-1]+B[P[i-1]];
}
ll ma=-INF;
for(int i=1;i<=N;i++){
chmax(ma,(Arui[i]+Brui[N]-Brui[i-1])*C[P[i-1]]);
}
if(chmin(ans,ma)) Pans=P;
}
}
for(int i=0;i<N;i++){
if(i) cout<<" ";
cout<<Pans[i]+1;
}
cout<<endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 10564kb
input:
2 4 1 1 4 5 1 5 1 9 1 9 8 1 9 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 8 3 2 7
output:
3 1 2 4 3 4 8 2 5 9 7 1 6
result:
ok correct
Test #2:
score: 0
Accepted
time: 2231ms
memory: 85440kb
input:
1 100000 581297 102863 1 742857 42686 1 676710 233271 1 443055 491162 1 442056 28240 1 769277 331752 1 8608 369730 1 495112 525554 1 787449 938154 1 441186 850694 1 84267 925450 1 740811 32385 1 834021 37680 1 257878 564126 1 90618 914340 1 239641 463103 1 40687 343062 1 587737 458554 1 103684 48666...
output:
70717 6151 48237 28851 35679 19561 94252 73342 13089 34865 69194 82763 50242 22597 3745 24913 97923 53671 77581 47428 82224 93567 61401 50007 4886 28731 54152 91278 99937 6691 26840 6048 46204 66044 60735 44469 20513 45842 18701 46818 27203 9261 50507 8020 72391 54368 86201 18839 64763 61758 40939 3...
result:
ok correct
Test #3:
score: 0
Accepted
time: 2241ms
memory: 85700kb
input:
1 99999 30245 831673 1 495617 185056 1 53028 422589 1 503558 778900 1 636981 480008 1 966864 78785 1 644954 303138 1 153080 225499 1 876411 832264 1 758904 549009 1 945000 441995 1 83780 789901 1 883282 832556 1 300776 548075 1 806599 108342 1 354979 831549 1 152110 819163 1 613891 812479 1 856259 6...
output:
47166 2741 21022 76386 87020 23829 32895 34086 8995 6472 88418 59894 49089 55715 33046 66377 34459 54653 20497 15160 30680 91245 81353 33829 28359 1966 17762 85616 83314 20870 86098 48631 85209 79444 7124 65569 7691 44641 23440 82099 10988 80962 25664 98304 22053 48400 54743 19064 17708 65861 82228 ...
result:
ok correct
Test #4:
score: -100
Wrong Answer
time: 2296ms
memory: 85468kb
input:
1 100000 361850 684411 2 188930 167748 2 676274 449963 1 970095 784305 1 412379 854673 1 208323 612179 1 296548 633970 1 560983 633064 2 848966 248363 2 741057 340814 1 393854 435721 2 302707 834494 1 229770 235051 2 875992 747523 2 314215 448795 1 531181 809914 2 786505 95721 1 86557 773136 1 44527...
output:
91401 4946 17471 17472 17473 4942 91381 4980 17392 17393 91406 17395 91404 17464 17401 17402 4977 17431 4976 97567 17409 17423 4968 17425 91394 17439 16952 16953 91585 5146 16962 16963 97495 4962 4961 17436 91389 97569 17445 17447 91386 4955 97577 5054 17456 4947 17458 91372 17462 4934 91328 17552 1...
result:
wrong answer Wrong Answer on Case#1