QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #571061 | #4791. Movies | Kevin5307 | WA | 1ms | 6316kb | C++23 | 1.8kb | 2024-09-17 20:16:16 | 2024-09-17 20:16:17 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
using i128=__int128;
void die(string S){puts(S.c_str());exit(0);}
int n,k;
int a[100100],b[200200];
int c[100100];
int psum[300300];
int pos[300300];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
pos[a[i]]=i;
memcpy(c,a,sizeof(c));
sort(c+1,c+n+1);
for(int i=1;i<=k;i++)
{
cin>>b[i];
psum[b[i]]++;
}
for(int i=1;i<=n+k;i++)
psum[i]+=psum[i-1];
int ans=k+1;
for(int l=1;l<=n;l++)
{
int r=l;
while(r<=n&&pos[c[r+1]]>pos[c[r]]) r++;
int L1=l-1,R1=n-r;
int L2=psum[c[l-1]],R2=k-psum[c[r+1]];
if(r==n) R2=0;
int M2=k-L2-R2;
int rr=max(L1*2,R1*2-1);
R1-=(M2+1)/2;
L1-=M2/2;
L1=max(L1,0);
R1=max(R1,0);
if(M2&1)
{
swap(L1,R1);
swap(L2,R2);
}
if(!L1&&!R1) ans=min(ans,rr);
if(R1&&!L1&&L2>=R1*2-2&&L2+R2>=R1*2-1) ans=min(ans,M2+R1*2-1);
if(L1&&!R1&&R2>=L1*2-1&&L2+R2>=L1*2) ans=min(ans,M2+L1*2);
if(R1&&L1+R1>1&&L2>=(R1-1)*2&&R2>=(R1-1+L1)*2-1&&L2+R2>=(R1-1)*2+(R1-1+L1)*2) ans=min(ans,M2+(R1-1)*2+(R1-1+L1)*2);
if(L1&&R2>=L1*2-1&&L2>=(R1+L1)*2-1&&L2+R2>=(R1+L1+L1)*2-1) ans=min(ans,M2+(R1+L1+L1)*2-1);
l=r;
}
if(ans>k) die("-1");
cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5908kb
input:
5 5 3 1 5 2 4 6 8 7 9 10
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 1ms
memory: 6068kb
input:
5 10 3 5 9 15 4 6 11 13 1 7 10 12 14 2 8
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5564kb
input:
5 10 14 15 4 12 1 3 9 6 10 13 2 11 7 5 8
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5860kb
input:
10 10 13 10 4 11 2 15 14 16 1 17 20 18 8 19 6 5 3 9 12 7
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5844kb
input:
10 10 20 3 17 8 10 6 18 15 14 19 11 9 13 16 4 7 12 5 1 2
output:
9
result:
ok 1 number(s): "9"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5624kb
input:
8 12 1 6 20 13 3 5 9 17 7 2 14 11 19 16 12 18 4 15 10 8
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 0ms
memory: 5624kb
input:
10 10 9 6 16 10 18 5 20 17 13 1 14 8 19 2 12 11 3 7 4 15
output:
7
result:
ok 1 number(s): "7"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
10 10 7 2 19 5 20 4 14 15 9 16 17 8 12 11 13 10 1 3 6 18
output:
9
result:
ok 1 number(s): "9"
Test #9:
score: 0
Accepted
time: 0ms
memory: 6012kb
input:
10 10 9 20 2 13 15 10 16 19 1 4 3 11 7 14 12 8 6 17 18 5
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 1ms
memory: 5920kb
input:
10 10 10 14 6 7 11 8 18 19 15 12 5 17 20 16 2 1 9 4 3 13
output:
-1
result:
ok 1 number(s): "-1"
Test #11:
score: 0
Accepted
time: 1ms
memory: 6244kb
input:
50 100 115 22 37 125 124 62 47 145 88 126 134 127 77 121 148 25 120 21 42 17 75 138 144 76 109 13 78 82 102 5 32 143 52 72 69 18 67 92 133 56 9 38 89 15 61 7 137 6 1 58 107 147 54 98 73 31 3 40 71 87 140 136 2 60 130 44 50 59 93 90 70 36 149 105 11 68 63 79 119 96 106 8 30 51 108 94 141 12 122 14 49...
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 1ms
memory: 5884kb
input:
50 100 69 63 30 79 36 27 46 57 28 98 19 15 18 75 77 76 86 74 131 78 60 33 11 40 24 116 71 109 23 111 99 87 58 103 132 119 55 66 122 54 128 43 130 147 94 125 90 144 105 148 89 51 41 84 81 88 100 12 82 17 118 126 93 143 101 64 145 3 134 5 13 62 7 6 133 31 26 138 16 2 129 110 65 102 108 114 35 10 115 9...
output:
-1
result:
ok 1 number(s): "-1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 5684kb
input:
50 100 72 7 130 30 87 104 4 32 11 46 111 49 35 124 12 67 36 26 13 143 45 92 33 8 125 148 59 127 114 55 68 41 98 83 19 99 108 28 47 115 90 135 15 56 65 48 93 101 138 84 22 6 121 40 57 53 37 105 116 34 21 75 64 80 70 16 5 91 73 9 103 25 2 71 58 61 86 133 120 137 150 126 94 134 119 147 97 82 18 145 42 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 5692kb
input:
50 100 32 24 115 62 144 61 118 21 84 68 9 30 114 79 27 19 147 75 35 73 4 90 71 111 140 18 88 81 26 102 59 78 77 103 16 138 12 33 145 150 44 148 107 28 11 42 124 109 143 128 38 31 131 97 58 104 25 76 41 15 74 43 53 110 85 70 57 91 92 80 86 5 83 64 96 116 95 133 93 1 105 139 66 141 37 23 14 50 106 113...
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 5856kb
input:
50 100 105 22 115 6 88 101 42 41 18 111 39 4 63 3 52 142 84 48 119 85 89 110 73 86 53 143 117 129 62 30 98 116 40 25 123 113 130 103 45 95 128 75 148 106 145 38 20 125 118 82 81 23 15 55 8 9 92 77 91 2 144 97 132 11 147 102 33 137 71 121 133 29 107 27 1 99 134 93 90 21 112 50 28 26 24 114 96 12 122 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #16:
score: 0
Accepted
time: 1ms
memory: 6316kb
input:
50 100 2 29 6 31 23 19 4 10 36 32 69 78 50 24 13 92 61 58 70 18 110 42 56 99 129 26 43 91 75 86 115 97 95 102 64 53 117 88 139 145 108 132 147 149 121 150 116 138 142 146 65 80 123 126 93 136 89 113 74 106 94 52 125 134 77 111 48 118 87 144 41 49 71 109 17 5 40 25 33 82 39 62 30 7 141 8 9 21 28 45 2...
output:
-1
result:
ok 1 number(s): "-1"
Test #17:
score: 0
Accepted
time: 1ms
memory: 5912kb
input:
50 100 2 5 9 12 14 15 20 21 22 26 33 30 34 36 38 42 44 43 47 49 48 55 57 60 67 69 75 79 78 81 82 85 90 100 91 99 108 109 112 116 124 115 119 125 127 129 143 148 147 150 17 16 80 102 11 3 25 142 23 137 131 7 123 110 54 65 118 113 19 149 92 56 29 46 31 70 96 77 106 146 120 53 37 84 95 134 141 139 72 7...
output:
80
result:
ok 1 number(s): "80"
Test #18:
score: 0
Accepted
time: 1ms
memory: 5692kb
input:
60 100 3 6 5 7 15 13 17 22 20 33 25 34 24 28 35 31 42 39 43 50 53 54 62 56 75 58 65 86 70 73 87 88 91 94 101 92 98 102 110 106 112 111 121 116 127 124 130 131 128 134 141 132 145 149 147 155 154 160 158 156 103 142 72 85 83 79 129 115 123 81 61 144 133 51 27 109 125 60 150 96 104 29 40 49 114 76 137...
output:
-1
result:
ok 1 number(s): "-1"
Test #19:
score: 0
Accepted
time: 1ms
memory: 6280kb
input:
60 200 12 3 13 17 30 22 19 49 33 47 43 55 56 57 80 82 90 81 113 106 111 124 118 123 135 139 133 140 137 138 147 152 141 150 154 166 165 186 170 173 185 189 187 195 198 196 212 197 210 213 228 230 231 242 235 240 243 250 247 254 208 73 36 34 163 102 161 159 221 69 18 164 76 63 153 206 239 224 28 184 ...
output:
87
result:
ok 1 number(s): "87"
Test #20:
score: 0
Accepted
time: 1ms
memory: 4280kb
input:
75 200 3 8 19 12 29 18 44 32 51 37 25 39 49 79 59 64 63 67 73 81 76 95 80 94 87 89 102 90 100 110 116 117 108 112 120 124 131 121 150 140 145 161 144 149 164 167 156 154 198 170 166 185 214 184 190 186 211 207 201 202 225 203 212 222 230 236 231 238 262 243 254 260 273 272 275 160 228 200 268 30 82 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #21:
score: -100
Wrong Answer
time: 1ms
memory: 5620kb
input:
75 225 12 13 15 36 23 38 49 39 53 51 52 72 76 64 55 66 80 89 75 92 99 83 90 114 96 111 101 107 135 104 146 112 126 152 120 137 153 160 162 151 159 163 171 165 161 169 203 177 209 190 219 248 229 222 210 237 254 256 239 241 260 255 245 274 262 261 276 289 270 286 287 297 294 299 300 148 236 73 154 68...
output:
173
result:
wrong answer 1st numbers differ - expected: '171', found: '173'