QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211869 | #6416. Classical Scheduling Problem | Liberty12619 | RE | 361ms | 55756kb | C++20 | 2.8kb | 2023-10-12 21:58:37 | 2023-10-12 21:58:37 |
Judging History
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...