QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#750348 | #9730. Elevator II | 552Hz# | RE | 0ms | 3852kb | C++17 | 1.5kb | 2024-11-15 14:13:15 | 2024-11-15 14:13:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cout<<#x<<": "<<x<<endl
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll=long long;
using ull=unsigned long long;
void solve(){
int n,f;
cin>>n>>f;
vector<int>a(n),b(n);
for(int i = 0;i<n;i++)
cin>>a[i]>>b[i];
vector<int>ord(n);
iota(ord.begin(),ord.end(),0);
sort(ord.begin(),ord.end(),[&](const int &i,const int &j){
if(b[i] == b[j])
return a[i] < a[j];
return b[i] < b[j];
});
int d = 0;
for(;d < n;d++)
{
if(b[ord[d]] >= f)
break;
}
for(;d - 1 >= 0;d--)
{
if(b[ord[d - 1]] < a[ord[d]])
break;
}
ll ans = 0;
int lst = f;
for(int k = d;k<n;k++)
{
int i = ord[k];
ans += (max(a[i] - lst,0) + b[i] - a[i]);
lst = b[i];
}
for(int k = 0;k < d;k++)
{
int i = ord[k];
ans += (max(a[i] - lst,0) + b[i] - a[i]);
lst = b[i];
}
cout<<ans<<endl;
for(int k = d;k<n;k++)
cout<<ord[k]+1<<" ";
for(int k = 0;k < d;k++)
cout<<ord[k]+1<<" ";
cout<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
}
/*
贡献法
正难则反
数小状压
关系连边
拆位
广义单调性
最长转最短
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3852kb
input:
2 4 2 3 6 1 3 2 7 5 6 2 5 2 4 6 8
output:
11 2 1 4 3 5 2 1
result:
ok ok 2 cases (2 test cases)
Test #2:
score: -100
Runtime Error
input:
6100 19 52 51 98 2 83 40 58 96 99 39 55 72 94 15 17 4 15 48 99 2 99 77 78 35 77 44 62 79 81 30 31 1 48 48 76 68 99 60 66 6 19 44 53 64 92 17 28 67 98 9 99 40 65 16 27 99 100 15 56 4 6 24 97 84 96 47 49 37 38 77 79 13 40 13 92 71 100 47 93 90 91 72 81 15 48 32 71 19 17 95 99 10 23 18 100 90 93 52 92 ...
output:
525 15 16 5 3 13 19 17 12 11 14 2 6 1 10 9 18 4 8 7 210 3 1 6 2 4 5 422 7 9 15 6 2 16 8 14 13 10 12 5 4 11 1 3 756 2 19 9 14 18 12 15 7 11 13 16 5 17 4 6 8 10 1 3 260 1 9 3 11 10 14 4 5 12 6 8 2 7 13 15 432 17 3 16 19 8 15 5 14 20 12 4 9 13 7 2 10 11 6 1 18 104 3 1 4 2 198 5 7 6 2 4 1 3 8 10 ...