QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211869#6416. Classical Scheduling ProblemLiberty12619RE 361ms55756kbC++202.8kb2023-10-12 21:58:372023-10-12 21:58:37

Judging History

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

  • [2023-10-12 21:58:37]
  • 评测
  • 测评结果:RE
  • 用时:361ms
  • 内存:55756kb
  • [2023-10-12 21:58:37]
  • 提交

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-1],root[0],1,num,x-1)+f[i].a;
			if(c<cost) {
				cost=c;
				pos=i;
			}
			continue;
		}
		if(n-i<k-x)	break;
		
		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;
	if(!check(1)) {
		cout<<0<<endl<<0<<endl;
		return ;
	}
	check(ans);
	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: 7628kb

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: 0
Accepted
time: 80ms
memory: 8088kb

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:

ok ok, 10000 test cases (10000 test cases)

Test #3:

score: 0
Accepted
time: 86ms
memory: 8008kb

input:

10000
31 13863446
88657 7
999554 9
118529 26
847277 28
370661 19
261018 28
635679 10
228483 3
645280 9
476021 13
778546 23
325779 9
833392 1
328146 30
873417 6
327100 31
9792 26
327533 31
361518 30
74201 17
220223 12
395716 28
92721 14
296968 27
177176 14
698707 6
130653 14
639654 14
883578 27
94779...

output:

29
30
17 20 1 23 3 27 25 21 8 6 24 12 19 5 22 10 31 7 28 9 26 11 13 4 15 29 30 2 14 16 
4
4
2 4 3 5 
2
2
2 3 
6
7
10 13 25 18 3 17 4 
6
6
8 9 10 12 2 5 
0
0
13
13
1 9 8 11 13 5 10 2 7 15 6 4 14 
7
7
6 3 1 5 8 7 10 
12
16
6 21 10 8 12 7 18 17 5 20 15 14 3 19 13 1 
21
24
3 21 16 11 8 14 23 2 4 26 1 15...

result:

ok ok, 10000 test cases (10000 test cases)

Test #4:

score: 0
Accepted
time: 89ms
memory: 8024kb

input:

10000
1 148649924
152343597 1
23 2873231053
341227727 2
97244309 22
382344096 18
92079917 18
716353906 4
963429195 14
131618841 1
637584871 10
210001357 11
578579097 4
246465963 6
968391199 2
950133297 8
509339869 18
427327942 11
542440792 6
451945776 11
62800058 4
275583515 14
347078482 12
49062133...

output:

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

result:

ok ok, 10000 test cases (10000 test cases)

Test #5:

score: 0
Accepted
time: 126ms
memory: 10148kb

input:

1000
82 7692098567
820091633 60
355742811 58
33274857 31
608429291 33
997797811 20
467502732 30
853286378 8
652795874 46
342018780 22
758395270 23
273397259 44
363579524 49
911951022 78
19637469 55
648691248 73
289596934 53
538807472 31
612554087 13
925583232 12
934115550 2
348467623 19
793103161 30...

output:

22
31
3 44 70 55 56 30 78 46 76 79 39 9 21 38 24 73 6 72 65 23 18 17 14 81 48 50 69 59 36 33 41 
333
338
209 291 121 124 245 155 159 179 200 57 251 132 163 284 119 69 105 268 25 260 206 300 207 117 228 304 127 14 44 281 214 233 108 311 263 294 232 205 59 168 279 140 160 306 248 62 52 314 315 254 246...

result:

ok ok, 1000 test cases (1000 test cases)

Test #6:

score: 0
Accepted
time: 198ms
memory: 17940kb

input:

100
1903 595649261976
242016788 1493
744829262 608
858593044 1816
156659209 1534
114991300 737
762579703 695
727190226 706
259042985 1281
43413203 314
845442517 462
566008000 1873
396423639 557
642518388 234
224641323 1517
952294191 985
706509300 1598
600896534 1474
40659577 676
385404080 236
626269...

output:

1277
1428
943 573 79 1221 326 496 868 130 555 169 1393 36 1305 650 1588 1784 1873 1017 1893 755 293 309 1106 1219 702 873 525 959 192 569 1228 968 1076 1080 1423 761 1169 1406 1652 859 221 1531 1356 506 581 528 28 1374 1789 1717 587 520 1448 413 1790 955 381 1575 947 1691 1833 1064 129 1719 18 1634 ...

result:

ok ok, 100 test cases (100 test cases)

Test #7:

score: 0
Accepted
time: 361ms
memory: 55756kb

input:

10
44263 8178145065835
144776695 4988
633784692 681
124897155 10140
486257408 37126
851769386 39526
842969054 41273
255566344 35680
453250390 22330
451088941 12204
619362016 38143
532744479 19473
674895021 28375
9336149 42718
66645534 4600
788583869 43466
74789962 44203
394416695 18040
400692349 209...

output:

18932
24298
17897 4413 4158 14060 43676 19100 21721 8162 30910 39141 14624 21509 31041 28256 29019 32495 27323 38853 13366 27931 28786 20149 11045 10832 23820 11055 38922 20269 30714 5769 22568 37604 19666 36323 21023 27197 34028 44062 10490 16638 20063 27639 20740 16242 6272 43260 22182 5668 260 35...

result:

ok ok, 10 test cases (10 test cases)

Test #8:

score: -100
Runtime Error

input:

1
200000 57702603292869
895088145 19931
718152698 145634
769081244 195129
55087510 17432
215103308 38922
856865039 8045
427652731 169525
293884192 171894
21414244 46946
623839144 178383
12560296 182397
24930343 41111
35462858 35129
835318852 151986
599094451 25610
510310473 182086
13017134 125354
31...

output:


result: