QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#571037#4791. MoviesKevin5307WA 1ms6256kbC++231.8kb2024-09-17 20:07:222024-09-17 20:07:23

Judging History

你现在查看的是最新测评结果

  • [2024-09-17 20:07:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6256kb
  • [2024-09-17 20:07:22]
  • 提交

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)*2&&L2+R2>=(R1+L1+L1)*2) ans=min(ans,M2+(R1+L1+L1)*2);
		l=r;
	}
	if(ans>k) die("-1");
	cout<<ans<<'\n';
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5932kb

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: 0ms
memory: 6088kb

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: 5992kb

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: 6256kb

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: 5628kb

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: 5632kb

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: 5924kb

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: 0ms
memory: 5892kb

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: 5696kb

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: 6096kb

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: 1ms
memory: 3988kb

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'