QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #767931 | #9730. Elevator II | wht11# | WA | 46ms | 3720kb | C++20 | 3.5kb | 2024-11-20 22:48:02 | 2024-11-20 22:48:10 |
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 ans = 0;
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)
{
// cerr << l << " " << r << "\n";
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({{l, r}, 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);
}
/* for (auto x : ans1)
{
cerr << x << endl;
} */
// cerr << ans << "\n";
int len = ve2.size();
int lst = k;
for (int i = 0; i < len; i++)
{
int l = ve2[i].first.first, r = ve2[i].first.second;
ans1.push_back(ve2[i].second);
// cerr << l << " " << r << " " << l - lst << " " << r - l << " " << lst << "\n";
if (l > lst)
ans += l - lst;
ans += r - l;
lst = r;
}
// cerr << ans << "\n";
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";
}
void check()
{
cin >> n >> k;
vector<pair<int, int>> ve;
int num = 0;
for (int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
ve.push_back({l, r});
num += r - l;
}
int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int mx = 1e9;
vector<int> aa;
do
{
int kk = k;
int ans = 0;
for (int i = 0; i < n; i++)
{
if (kk < ve[a[i] - 1].first)
ans += ve[a[i] - 1].first - kk;
if (a[0] == 1 && a[1] == 2 && a[2] == 3 && a[3] == 4 && a[4] == 7 && a[5] == 6 && a[6] == 8 && a[7] == 5)
{
cerr << ans << endl;
}
kk = ve[a[i] - 1].second;
}
if (ans < mx)
{
mx = ans;
aa.clear();
for (int i = 0; i < n; i++)
{
aa.push_back(a[i]);
}
}
} while (next_permutation(a, a + n));
cout << mx + num << "\n";
for (auto x : aa)
cout << x << " ";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
// check();
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3568kb
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: 46ms
memory: 3720kb
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)