QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211785#6416. Classical Scheduling ProblemLiberty12619WA 94ms7860kbC++202.8kb2023-10-12 21:15:132023-10-12 21:15:13

Judging History

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

  • [2023-10-12 21:15:13]
  • 评测
  • 测评结果:WA
  • 用时:94ms
  • 内存:7860kb
  • [2023-10-12 21:15:13]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl '\n'
#define PII pair<int,int>
using namespace std;
const int N = 2e5+10;
int A[N],root[N],num,pos;
struct node {
	int a,b,id;
}f[N];
struct node1 {
	int l,r,cnt,sum,val;
}t[N*20];
bool cmp(node a,node b) {
	return a.b<b.b;
}
int n,tim,idx;
void build(int &now,int l,int r) {
	now=++idx;
	t[now].cnt=t[now].sum=t[now].val=0;
	if(l==r) return ;
	int mid=l+r>>1;
	build(t[now].l,l,mid);
	build(t[now].r,mid+1,r);
}
void modify(int &now,int pre,int l,int r,int p,int val) {
	now=++idx;
	t[now]=t[pre];
	t[now].cnt++,t[now].sum+=val;
	if(l==r) {
		t[now].val=val;
		return ;
	}
	int mid=l+r>>1;
	if(p<=mid) modify(t[now].l,t[pre].l,l,mid,p,val);
	else modify(t[now].r,t[pre].r,mid+1,r,p,val);
}
int query(int now,int pre,int l,int r,int k) {
	if(l==r) return t[now].val*k;
	int mid=l+r>>1;
	int res=t[t[now].l].cnt-t[t[pre].l].cnt;
	if(res>=k) return query(t[now].l,t[pre].l,l,mid,k);
	else {
		return query(t[now].r,t[pre].r,mid+1,r,k-res)+t[t[now].l].sum-t[t[pre].l].sum;
	}
}
int getid(int x) {
	return lower_bound(A+1,A+num+1,x)-A;
}
bool check(int x) {
	int cost=1e18;
	for(int i=x;i<=n;i++) {
		int k=f[i].b;
		if(k<=x) {
		    int c=query(root[i],root[0],1,num,x);
			if(c<cost) {
				cost=c;
				pos=i;
			}
			continue;
		}
		int res1=query(root[i-1],root[0],1,num,x-1);
		int res2=query(root[n],root[i],1,num,k-x);
		if(res1+res2+f[i].a<cost) {
			cost=res1+res2+f[i].a;
			pos=i;
		}
	}
	if(cost>tim) return false;
	else return true;
}
void solve()
{
	cin>>n>>tim;
	for(int i=1;i<=n;i++) {
		cin>>f[i].a>>f[i].b;
		f[i].id=i;
	}
	sort(f+1,f+n+1,cmp);
	for(int i=1;i<=n;i++) A[i]=f[i].a;
	sort(A+1,A+n+1);
	num=unique(A+1,A+n+1)-A-1;
	idx=pos=0;
	build(root[0],1,num);
	for(int i=1;i<=n;i++) {
		int p=getid(f[i].a);
		modify(root[i],root[i-1],1,num,p,f[i].a);
	}
	int ans=0;
	int l=1,r=n;
	while(l<=r) {
		int mid=l+r>>1;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	vector<int> v;
	int pos1=pos;
	if(!check(1)) {
		cout<<0<<endl<<0<<endl;
		return ;
	}
	pos=pos1;
	priority_queue<PII> q;
	for(int i=1;i<pos;i++) q.push({-f[i].a,f[i].id});
	int cnt=0;
	while(cnt<ans-1&&q.size()) {
		auto p=q.top();
		q.pop();
		int x=p.y;
		v.push_back(x);
		cnt++;
	}
	v.push_back(f[pos].id);
	if(f[pos].b>ans) {
		while(q.size()) q.pop();
		for(int i=pos+1;i<=n;i++) q.push({-f[i].a,f[i].id});
		cnt=0;
		while(cnt<f[pos].b-ans) {
			auto p=q.top();
			q.pop();
			int x=p.y;
			v.push_back(x);
			cnt++;
		}
	}
	cout<<ans<<endl;
	cout<<v.size()<<endl;
	for(int x:v) cout<<x<<" ";
	cout<<endl;
}
signed main()
{
	int T = 1;
	cin.tie(0)->sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}

详细

Test #1:

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

input:

2
4 100
20 1
40 4
60 3
30 3
1 5
10 1

output:

2
3
1 4 2 
0
0

result:

ok ok, 2 test cases (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 94ms
memory: 7860kb

input:

10000
21 1892
174 13
604 15
170 2
413 11
899 2
531 12
651 17
553 9
429 8
837 14
937 12
577 7
532 11
19 2
173 10
165 6
762 15
221 6
945 13
302 19
7 3
54 26066
812 31
432 24
240 37
171 39
204 47
174 30
569 1
467 5
624 42
734 35
907 3
568 23
802 40
991 32
119 13
187 27
739 42
891 14
550 44
374 16
483 1...

output:

7
8
21 14 16 3 18 12 9 15 
53
53
22 25 37 41 15 27 4 6 48 16 54 29 5 31 3 38 42 43 44 51 35 20 2 8 30 21 52 19 34 12 7 26 9 53 33 36 46 47 10 49 24 17 40 45 39 13 1 32 23 18 50 11 28 
12
12
5 12 14 4 6 1 8 7 15 2 13 16 
7
15
40 8 28 41 14 13 29 38 21 37 24 11 43 33 26 
10
10
7 12 9 10 29 19 5 28 22 ...

result:

wrong answer too much time taken to learn the topics: 6410 > 6229 (test case 11)