QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#688577 | #7750. Revenge on My Boss | icpc_zhzx034# | WA | 434ms | 8836kb | C++14 | 1.9kb | 2024-10-30 11:10:53 | 2024-10-30 11:10:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> Pr;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
// #define mid ((l+r)>>1)
#define popcnt __builtin_popcountll
const ll mod = 998244353;
inline ll read(){
ll x=0, f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
return x*f;
}
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline ll qpow(ll a,ll b){
ll ans=1, base=a;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod; b>>=1;
}
return ans;
}
void init(){ }
ll n,a[100005],b[100005],c[100005],S,ans[100005];
struct Node{
ll p,q,id;
Node(ll a=0,ll b=0,ll c=0){ p=a, q=b, id=c; }
};
vector<Node>v1, v2;
bool check(ll mid){
v1.clear(), v2.clear();
for(ll i=1;i<=n;i++){
ll w = mid - (a[i]+S)*c[i], p = a[i]-b[i], q;
if(w >= 0) q = w/c[i];
else if((-w)%c[i]==0) q = w/c[i];
else q = w/c[i]-1;
if(p <= 0) v1.pb(Node(p,q,i));
else v2.pb(Node(p,q,i));
}
sort(v1.begin(), v1.end(), [](Node A, Node B){
return A.q > B.q;
});
sort(v2.begin(), v2.end(), [](Node A, Node B){
return A.p-A.q > B.p-B.q;
});
ll now=0, tp=0;
for(auto N: v1){ if(now > N.q) return 0; now += N.p; }
for(auto N: v2){ if(now > N.q) return 0; now += N.p; }
for(auto N: v1) ans[++tp] = N.id;
for(auto N: v2) ans[++tp] = N.id;
return 1;
}
void procedure(){
n=read();
for(ll i=1;i<=n;i++){
a[i]=read(), b[i]=read(), c[i]=read();
S+=b[i];
}
ll l=1, r=2e18;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
}else l=mid+1;
}
for(ll i=1;i<=n;i++) printf("%lld ", ans[i]); puts("");
}
int main(){
#ifdef LOCAL
assert(freopen("input.txt","r",stdin));
assert(freopen("output.txt","w",stdout));
#endif
ll T=read();
init();
while(T--) procedure();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5948kb
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 8 4 2 5 9 7 1 6
result:
ok correct
Test #2:
score: 0
Accepted
time: 429ms
memory: 8836kb
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: -100
Wrong Answer
time: 434ms
memory: 8720kb
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:
42779 26176 16432 93736 36110 21022 69840 33300 88899 48735 24934 97468 58044 16598 54398 41611 25297 90410 54385 38513 14754 7374 40518 45724 3741 95478 36354 5270 92123 87433 5901 57489 42968 40570 60847 61715 65894 68944 27887 3727 38578 14748 15072 79314 41234 42830 79639 35429 60443 63782 12370...
result:
wrong answer Wrong Answer on Case#1