QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#264518#7750. Revenge on My Bossdaydream#WA 2590ms16240kbC++202.8kb2023-11-25 14:15:532023-11-25 14:15:54

Judging History

你现在查看的是最新测评结果

  • [2023-11-25 14:15:54]
  • 评测
  • 测评结果:WA
  • 用时:2590ms
  • 内存:16240kb
  • [2023-11-25 14:15:53]
  • 提交

answer

#include<bits/stdc++.h>
#define db double
#define LL long long
#define ldb long double
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define pli pair<LL,int>
#define pii pair<int,int>
#define pip pair<int,pii>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int infi=1e9;
const LL infl=1e18;
const ldb eps=1e-9;

struct Seg_Tree
{
	int n;
	vector<pii> tr;
	vector<set<pli,greater<pli>>> st;
	Seg_Tree() {n=0;}
	Seg_Tree(int N)
	{
		n=N;
		tr.resize(n*4+10,mp(-infi,0));
		st.resize(n);
	}
	#define mid ((l+r)>>1)
	void insert(int x,int l,int r,int p,pii v)
	{
		if(l==r)
		{
			st[l].insert(v);
			tr[x]=*st[l].begin();
			return ;
		}
		if(p<=mid) insert(x<<1,l,mid,p,v);
		else insert(x<<1|1,mid+1,r,p,v);
		tr[x]=max(tr[x<<1],tr[x<<1|1]);
	}
	void erase(int x,int l,int r,int p,pii v)
	{
		if(l==r)
		{
			st[l].erase(v);
			if(st[l].empty()) tr[x]=mp(-infi,0);
			else tr[x]=*st[l].begin();
			return ;
		}
		if(p<=mid) erase(x<<1,l,mid,p,v);
		else erase(x<<1|1,mid+1,r,p,v);
		tr[x]=max(tr[x<<1],tr[x<<1|1]);
	}
	pii query(int x,int l,int r,int p)
	{
		if(p<=l) return tr[x];
		pii res=query(x<<1|1,mid+1,r,p);
		if(p<=mid) res=max(res,query(x<<1,l,mid,p));
		return res;
	}
	#undef mid 
	void ins(int p,int v,int i) {insert(1,0,n-1,p,mp(v,i));}
	void del(int p,int v,int i) {erase(1,0,n-1,p,mp(v,i));}
	pii qry(int p) {return query(1,0,n-1,p);}
};
typedef tuple<LL,int,int> tup;
int n;
void solve()
{
	cin>>n;vector<int> a(n+1,0),b(n+1,0),c(n+1,0);
	for(int i=1;i<=n;++i) cin>>a[i]>>b[i]>>c[i];
	vector<int> ans(n+1,0);
	LL l=0,r=infl,res=infl;
	auto check=[&](LL v)
	{
		vector<LL> val,w(n+1,0);
		LL s=0;set<tup> st;
		for(int i=1;i<=n;++i)
		{
			w[i]=v/c[i]-a[i];
			s+=b[i];
			if(b[i]-a[i]>=0) val.pb(w[i]);
			else st.insert({w[i],a[i]-b[i],i});
		}
//		cout<<"ok\n";
		sort(val.begin(),val.end());val.erase(unique(val.begin(),val.end()),val.end());
		Seg_Tree T(val.size());
		int m=0;
		for(int i=1;i<=n;++i)
			if(b[i]-a[i]>=0)
			{
				++m;
				T.ins(w[i]=lower_bound(val.begin(),val.end(),w[i])-val.begin(),b[i]-a[i],i);
			}
		for(int i=1;i<=m;++i)
		{
			int p=lower_bound(val.begin(),val.end(),s)-val.begin();
			auto [W,P]=T.qry(p);
			if(!P) return 0;
			ans[i]=P;s-=W;T.del(w[P],W,P);
		}
		for(auto [W,V,P]:st)
		{
			if(s>W) return 0;
			s+=V;ans[++m]=P;
		}
		return 1;
	};
	while(l<=r)
	{
		LL mid=(l+r)>>1;
		if(check(mid)) res=mid,r=mid-1;
		else l=mid+1;
	}
//	cout<<res<<'\n';
	check(res);
	for(int i=1;i<=n;++i) cout<<ans[i]<<' ';
	cout<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int TT=1;
	cin>>TT;
	for(;TT;--TT) solve();
	return 0;
}
/*
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

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3588kb

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 2 4 5 9 7 1 6 

result:

ok correct

Test #2:

score: 0
Accepted
time: 2405ms
memory: 16192kb

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 77582 77581 82112 72163 18220 43645 30468 80107 54173 17444 14872 8630 50133 26305 35 70096 40298 10072 56385 75312 79444 19284 81622 95793 96892 82320 8443 11434 56765 72103 89089 86041 48305 32033 88191 83243 9383 66880 81866 31386 23642 79775 66240 99937 38682 18931 39524 48449 36540 202 11...

result:

ok correct

Test #3:

score: -100
Wrong Answer
time: 2590ms
memory: 16240kb

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:

11258 2014 71474 6532 89436 65068 47750 70417 79857 12956 68243 43016 12061 58424 14146 76212 48267 28786 37433 26941 97091 5811 25880 29667 49639 53925 51067 45765 35831 93900 12972 7028 92312 21851 10387 35976 17613 69792 36607 32905 38051 15744 66643 51156 90652 31627 58121 50418 29341 27066 7374...

result:

wrong answer Wrong Answer on Case#1