QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #571043 | #4791. Movies | Kevin5307 | WA | 1ms | 6260kb | C++23 | 1.8kb | 2024-09-17 20:10:28 | 2024-09-17 20:10:28 |
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=n+n;
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-1)*2&&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: 0ms
memory: 5660kb
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: 5592kb
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: 0ms
memory: 5652kb
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: 5992kb
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: 5596kb
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: 5832kb
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: 6260kb
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: 6016kb
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: 1ms
memory: 6068kb
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: 0ms
memory: 5660kb
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: -100
Wrong Answer
time: 0ms
memory: 5660kb
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:
100
result:
wrong answer 1st numbers differ - expected: '-1', found: '100'