QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#821762 | #9059. Item Selection | WeaRD276# | AC ✓ | 1ms | 3884kb | C++20 | 2.3kb | 2024-12-19 17:55:19 | 2024-12-19 17:55:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define x first
#define y second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define int ll
typedef long long ll;
typedef double db;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
typedef pair<ll, ll> pll;
int solve()
{
int n, m, s, p, q;
if (!(cin >> n >> m >> s >> p >> q))
return 1;
s--;
vector<int> pre(p), need(q);
FOR (i, 0, p)
{
cin >> pre[i];
pre[i]--;
}
FOR (i, 0, q)
{
cin >> need[i];
need[i]--;
}
int ans = 1e9;
int pages = (n + m - 1) / m;
//sort(all(pre));
//sort(all(need));
set<int> preS(all(pre));
set<int> needS(all(need));
vector<int> forPage(pages);
vector<int> was;
//cerr << "pages = " << pages << '\n';
FOR (i, 0, pages)
{
int vyb = 0, pot = 0, sp = 0;
for (int j = i * m; j < i * m + m && j < n; j++)
{
if (preS.count(j))
vyb++;
if (needS.count(j))
pot++;
if (preS.count(j) && needS.count(j))
sp++;
}
//cerr << "i = " << i << " vyb = " << vyb << " pot = " << pot << " sp = " << sp << '\n';
int cur = vyb + pot - 2 * sp;
cur = min(cur, 1 + pot);
if (i != pages - 1 || n % m == 0)
cur = min(cur, 1 + m - pot);
else
cur = min(cur, 1 + (n % m) - pot);
forPage[i] = cur;
if (cur != 0)
was.pb(i);
}
int totPages = 0;
FOR (i, 0, sz(was))
totPages += forPage[was[i]];
if (was.empty())
{
cout << "0\n";
return 0;
}
//FOR (i, 0, sz(was))
//{
//int j = was[i];
//cerr << "j = " << j << " forPage = " << forPage[j] << '\n';
//}
int fir = min(was[0], s);
int las = max(was.back(), s);
ans = min(ans, totPages + 2 * (s - fir) + las - s);
ans = min(ans, totPages + 2 * (las - s) + s - fir);
cout << ans << '\n';
return 0;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int TET = 1e9;
//cin >> TET;
for (int i = 1; i <= TET; i++)
{
if (solve())
{
break;
}
#ifdef ONPC
cerr << "_____________________________\n";
#endif
}
#ifdef ONPC
cerr << "\nfinished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec\n";
#endif
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
input:
11 4 1 5 5 1 4 9 10 11 1 3 6 7 8
output:
7
result:
ok single line: '7'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
1 1 1 1 0 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
1 1 1 0 0
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
1000 17 20 0 0
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
7 7 1 3 3 2 4 7 2 4 7
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
7 2 1 3 3 2 4 7 2 4 7
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
1000 1 100 1 1 400 700
output:
602
result:
ok single line: '602'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
1000 1 900 1 1 400 700
output:
502
result:
ok single line: '502'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1000 1 650 1 1 400 700
output:
352
result:
ok single line: '352'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
1000 1 450 1 1 400 700
output:
352
result:
ok single line: '352'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
103 5 10 10 10 1 2 3 4 5 11 13 15 16 21 6 7 8 9 10 12 14 17 30 101
output:
39
result:
ok single line: '39'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
10 3 4 5 0 1 2 3 4 5
output:
5
result:
ok single line: '5'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
10 3 4 0 5 1 2 3 4 5
output:
6
result:
ok single line: '6'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
1000 1 500 0 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...
output:
2498
result:
ok single line: '2498'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
1000 1 500 500 500 1 2 3 4 5 6 10 12 13 15 17 18 19 20 23 24 25 26 29 32 35 37 38 41 50 52 53 56 60 61 62 65 66 67 68 70 71 72 73 75 80 83 87 89 90 91 93 94 95 96 97 99 100 101 104 105 106 107 110 111 113 117 120 121 122 123 125 127 128 129 130 138 139 140 141 142 146 148 151 155 156 157 159 160 162...
output:
1988
result:
ok single line: '1988'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
1000 3 150 500 500 4 5 7 8 11 12 17 18 20 22 26 27 30 31 33 35 36 37 39 43 45 47 48 49 52 53 57 60 64 65 66 70 76 79 80 82 83 84 87 89 92 93 94 97 98 101 103 105 106 107 108 110 113 114 115 118 120 122 123 126 128 131 135 141 143 146 147 149 151 152 153 156 158 159 160 163 164 166 168 170 172 173 17...
output:
876
result:
ok single line: '876'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
1000 17 1 250 250 1 3 5 6 7 8 12 17 28 30 34 41 43 53 54 56 58 60 64 66 72 73 79 80 83 96 97 101 104 109 110 111 115 116 118 119 122 125 126 130 134 135 136 137 142 147 149 150 154 158 165 168 170 180 182 184 186 187 191 193 195 196 198 200 203 204 207 209 211 212 219 225 228 230 232 233 235 238 242...
output:
354
result:
ok single line: '354'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
1000 17 30 250 250 1 8 18 33 36 43 57 58 65 68 75 81 83 86 87 96 97 100 105 107 114 119 122 133 134 135 136 139 141 142 144 145 146 148 150 155 157 160 166 177 179 180 182 184 185 189 191 200 201 202 209 218 220 224 228 230 238 239 240 245 246 251 261 262 263 264 265 276 279 280 282 286 288 290 292 ...
output:
365
result:
ok single line: '365'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1000 17 59 250 250 2 7 10 13 14 15 20 26 27 37 39 41 42 48 54 59 61 63 66 69 71 73 74 75 78 90 97 104 109 115 121 128 132 135 140 142 149 150 154 157 159 160 166 169 173 182 186 187 190 198 206 207 214 215 216 217 225 237 241 249 254 260 263 273 276 277 280 287 292 297 299 300 302 312 316 319 326 32...
output:
347
result:
ok single line: '347'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
1000 320 2 500 500 1 2 8 11 12 13 15 17 18 20 21 22 24 28 31 34 37 38 39 40 42 45 46 52 54 56 60 64 67 68 70 74 75 77 78 79 80 81 83 85 87 88 89 90 91 96 97 99 101 103 104 106 107 110 116 117 121 122 124 125 127 129 131 132 133 135 136 139 140 142 143 144 145 146 147 149 151 152 153 156 158 162 164 ...
output:
480
result:
ok single line: '480'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
1000 743 1 500 500 1 5 7 10 14 17 22 23 24 28 31 35 36 37 38 39 40 48 50 52 53 54 55 56 58 60 62 63 64 68 69 71 72 74 76 80 81 82 83 84 88 90 92 93 94 95 96 99 100 101 103 104 105 106 107 108 112 113 114 116 117 118 119 120 121 122 125 126 128 130 133 134 137 138 139 141 143 144 146 147 148 149 155 ...
output:
481
result:
ok single line: '481'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
1000 743 2 500 500 3 4 7 10 13 14 19 20 22 24 25 28 29 30 31 32 34 37 39 41 43 48 49 50 51 54 57 59 61 62 68 69 71 72 76 78 80 83 84 87 88 91 92 94 97 98 100 102 104 106 107 108 110 111 112 113 115 116 119 122 125 126 128 129 132 135 136 138 139 143 144 145 148 150 152 153 154 156 158 159 160 162 16...
output:
468
result:
ok single line: '468'