QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #767702 | #9730. Elevator II | wht11# | WA | 51ms | 3968kb | C++20 | 2.2kb | 2024-11-20 21:47:58 | 2024-11-20 21:47:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 10;
int n, k;
void solve()
{
cin >> n >> k;
vector<pair<pair<int, int>, int>> ve;
for (int i = 1; i <= n; i++)
{
int l, r;
cin >> l >> r;
ve.push_back({{l, r}, i});
}
sort(ve.begin(), ve.end());
int st = k;
int ans = 0;
int kk = k;
vector<int> vis(n + 1, 0);
vector<int> ans1;
for (auto tmp : ve)
{
int l = tmp.first.first, r = tmp.first.second;
if (l <= k)
{
if (r >= k)
{
k = r;
vis[tmp.second] = 1;
ans1.push_back(tmp.second);
}
}
}
vector<pair<pair<int, int>, int>> ve1;
vector<pair<pair<int, int>, int>> vv;
for (auto tmp : ve)
{
int l = tmp.first.first, r = tmp.first.second;
if (l <= k)
{
if (vis[tmp.second] == 0)
vv.push_back({{r, l}, tmp.second});
ans += r - l;
}
else
ve1.push_back({{r, l}, tmp.second});
}
int mx = 0;
vector<pair<pair<int, int>, int>> ve2;
for (auto tmp : ve1)
{
int l = tmp.first.first, r = tmp.first.second;
if (r <= mx)
{
vv.push_back({{r, l}, tmp.second});
ans += r - l;
}
else
ve2.push_back({{l, r}, tmp.second});
mx = max(mx, r);
}
int len = ve2.size();
int lst = k;
for (int i = 0; i < len; i++)
{
int r = ve2[i].first.first, l = ve2[i].first.second;
ans1.push_back(ve2[i].second);
ans += abs(l - lst);
ans += r - l;
lst = r;
}
sort(vv.begin(), vv.end(), greater<pair<pair<int, int>, int>>());
len = vv.size();
for (int i = len - 1; i >= 0; i--)
ans1.push_back(vv[i].second);
cout << ans << "\n";
for (auto x : ans1)
cout << x << " ";
cout << "\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
2 4 2 3 6 1 3 2 7 5 6 2 5 2 4 6 8
output:
11 2 3 1 4 5 2 1
result:
ok ok 2 cases (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 51ms
memory: 3968kb
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:
524 2 10 9 18 4 8 7 15 16 5 3 13 19 17 12 11 14 6 1 194 5 3 1 6 2 4 397 9 10 4 11 1 3 7 15 6 2 16 8 14 13 12 5 733 2 9 15 7 11 3 19 14 18 12 13 16 5 17 4 6 8 10 1 244 3 11 10 14 5 6 2 7 13 15 1 9 4 12 8 422 17 18 3 16 19 8 15 5 14 20 12 4 9 13 7 2 10 11 6 1 104 3 4 2 1 187 4 1 3 8 10 9 5 7 6 ...
result:
wrong answer Participant declares the cost to be 524, but the plan actually costs 538 (test case 1)