QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#821776 | #9059. Item Selection | LaVuna47# | AC ✓ | 1ms | 3984kb | C++17 | 2.9kb | 2024-12-19 18:03:13 | 2024-12-19 18:03:13 |
Judging History
answer
/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, st_, n) for(ll i = st_; i < n; ++i)
#define RFOR(i, n, end_) for(ll i = (n)-1; i >= end_; --i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
struct Page
{
ll l, r;
set<ll> want;
set<ll> has;
ll answ;
ll plain(const set<ll>& W, const set<ll>& H)
{
ll res =0;
for(auto el: W)
{
if(H.find(el) == H.end())
++res;
}
for(auto el: H)
{
if(W.find(el) == W.end())
++res;
}
return res;
}
ll comp_answ()
{
ll res =1e16;
// select
{
set<ll> H;
FOR(i,l,r+1)H.insert(i);
res=min(res,1+plain(want,H));
}
// deselect
{
set<ll> H;
res=min(res,1+plain(want,H));
}
// none
res = min(res, plain(want,has));
return answ=res;
}
};
int solve()
{
ll n,m,s,p,q;
if(!(cin>>n>>m>>s>>p>>q))return 1;
--s;
vector<int> a;
vector<int> b;
a=vector<int>(p); // preselected
b=vector<int>(q); // I want
FOR(i,0,p)cin>>a[i];
FOR(i,0,q)cin>>b[i];
vector<Page> pages;
FOR(i,0,n+4)
{
Page pg;
pg.l = i*m+1, pg.r=(i+1)*m;
FOR(j,0,p)
if(a[j]>=pg.l && a[j] <= pg.r)
pg.has.insert(a[j]);
FOR(j,0,q)
if(b[j]>=pg.l && b[j] <= pg.r)
pg.want.insert(b[j]);
if(pg.r >= n)
{
pg.r=n;
}
pg.comp_answ();
//cout<<pg.answ<<' ';
pages.pb(move(pg));
if(pg.r == n) break;
}
ll L = 0;
while(L < sz(pages) && pages[L].answ==0)++L;
ll R = sz(pages)-1;
while(R >= 0 && pages[R].answ==0)--R;
ll res=0;
for(auto& pg: pages)
res += pg.answ;
if(res==0)
{
cout<<res<<'\n';
return 0;
}
if(s >= L && s <= R)
{
ll r1 = 2*(s-L) + R-s;
ll r2 = 2*(R-s) + s-L;
res += min(r1, r2);
}
else
{
res += max(R-s, s-L);
}
cout<<res<<'\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
cout << "__________________________" << endl;
#endif
}
#ifdef ONPC
cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
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: 3488kb
input:
1 1 1 1 0 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 1 1 0 0
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
1000 17 20 0 0
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3656kb
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: 3580kb
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: 1ms
memory: 3896kb
input:
1000 1 100 1 1 400 700
output:
602
result:
ok single line: '602'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
1000 1 900 1 1 400 700
output:
502
result:
ok single line: '502'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
1000 1 650 1 1 400 700
output:
352
result:
ok single line: '352'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
1000 1 450 1 1 400 700
output:
352
result:
ok single line: '352'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3564kb
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: 3552kb
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: 3536kb
input:
10 3 4 0 5 1 2 3 4 5
output:
6
result:
ok single line: '6'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3984kb
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: 0ms
memory: 3932kb
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: 3668kb
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: 1ms
memory: 3600kb
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: 1ms
memory: 3608kb
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: 1ms
memory: 3568kb
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: 3584kb
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: 3568kb
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: 3844kb
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'