QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207641#6769. Monster Hunterveg#AC ✓15ms6636kbC++232.3kb2023-10-08 18:17:102023-10-08 18:17:10

Judging History

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

  • [2023-10-08 18:17:10]
  • 评测
  • 测评结果:AC
  • 用时:15ms
  • 内存:6636kb
  • [2023-10-08 18:17:10]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=1e5+5;
int  n,m,a[N],b[N],c[N],sum,s[N][5];
bool check(ll x) { //x=ksum+b
	ll k=x/n,yu=x%n;
	ll s1=k*s[n][1]+s[yu][1],s2=k*s[n][2]+s[yu][2],s3=k*s[n][3]+s[yu][3];
	for(int i=1;i<=m;++i) {
		c[i]=b[i];
		if(s3&&(b[i]&1)&&(b[i]>1)) b[i]-=3,s3--;
	}
/*	printf("%d %d %d\n",s1,s2,s3);
	for(int i=1;i<=m;++i) {
		printf("%d ",b[i]);
	}
	puts("");*/
	if(s3) {
		for(int i=1;i<=m;++i) {
			if((b[i]/6)*2<=s3) {
				s3-=(b[i]/6)*2;
				b[i]%=6;
			} else {
				b[i]-=6*(s3/2);
				s3%=2;
				break;
			}
		}
	}
/*	printf("%d %d %d\n",s1,s2,s3);
	for(int i=1;i<=m;++i) {
		printf("%d ",b[i]);
	}
	puts("");*/
	if(s3) {
		for(int i=1;i<=m;++i) {
			if(b[i]>3) {
				b[i]-=3;
				s3--;
				if(s3==0) break;
			}
		}
	}
	s2+=s3; s3=0;
/*	printf("%d %d %d\n",s1,s2,s3);
	for(int i=1;i<=m;++i) {
		printf("%d ",b[i]);
	}
	puts("");*/
/*	if(s3) {
		for(int i=1;i<=m;++i) {
			if(b[i]==2) {
				s3--;
				b[i]=0;
				if(s3==0) break;
			}
		}
	}
	if(s3) {
		for(int i=1;i<=m;++i) {
			if(b[i]==1) {
				s3--;
				b[i]=0;
				if(s3==0) break;
			}
		}
	}*/
/*	printf("%d %d %d\n",s1,s2,s3);
	for(int i=1;i<=m;++i) {
		printf("%d ",b[i]);
	}
	puts("");*/
	if(s2) {
		for(int i=1;i<=m;++i) {
			if(b[i]/2<=s2) {
				s2-=b[i]/2;
				b[i]%=2;
				if(s2==0) break;
			} else {
				b[i]-=s2*2;
				s2=0;
				break;
			}
		}
	}
	if(s2) {
	for(int i=1;i<=m;++i) {
			assert(b[i]<=1);
	}
	}
	if(s2) {
		for(int i=1;i<=m;++i) {
			if(b[i]&&s2) {
				s2--; b[i]=0;
				if(s2==0) break;
			}
		}
	}
	for(int i=1;i<=m;++i ){
		if(b[i]>0) s1-=b[i],b[i]=0;
		assert(b[i]==0);
	}
	for(int i=1;i<=m;++i) b[i]=c[i];
	return s1>=0;
}
int main() {
//	freopen("1.in","r",stdin);
	int T; scanf("%d",&T);
	while(T--) {
		scanf("%d",&n);
		for(int i=1;i<=n;++i) {
			scanf("%d",&a[i]);
			for(int j=1;j<=3;++j) {
				s[i][j]=s[i-1][j]+(a[i]==j);
			}
		}
		scanf("%d",&m); 
		ll l=0,r=0;
		for(int i=1;i<=m;++i) {
			scanf("%d",&b[i]); r+=b[i];
		}
		sum=s[n][1]+2*s[n][2]+3*s[n][3];
		l=1,r=1e14; ll ans=0;
	//	printf("%d\n",check(4));
	//	printf("%lld %lld\n",l,r);
		while(l<=r) {
			ll mid=l+r>>1;
			if(check(mid)) {
				ans=mid,r=mid-1;
			} else l=mid+1;
		}
		printf("%lld\n",ans); 
	}
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3820kb

input:

2
2
3 2
3
2 4 2
5
1 2 3 2 1
2
3 3

output:

4
3

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

100
21
1 3 3 3 2 3 3 2 2 1 3 2 1 3 2 1 1 1 3 3 3
3
3 3 1
19
1 3 1 1 3 3 1 3 2 3 2 2 3 3 1 1 2 2 2
10
2 2 3 1 5 2 2 5 5 3
8
1 3 3 1 3 2 3 1
3
1 2 1
27
1 1 1 2 1 3 1 2 2 3 3 3 1 1 1 1 2 1 2 2 2 2 3 2 1 3 2
4
5 1 2 2
23
2 1 3 2 3 2 2 3 1 2 1 3 1 2 3 1 3 1 2 2 2 1 1
10
4 3 5 4 5 4 1 4 3 4
8
1 2 1 3 2 3 ...

output:

3
15
3
7
19
12
3
8
7
20
5
10
6
10
3
10
16
1
5
6
10
14
13
8
8
5
13
15
5
10
16
14
10
1
10
4
3
16
5
4
7
8
7
5
13
10
10
10
14
3
9
8
19
16
8
25
11
21
2
3
14
12
4
12
17
22
11
3
14
15
2
9
12
7
3
9
4
9
11
2
2
5
5
3
2
2
4
6
7
10
3
14
2
1
5
4
8
13
14
16

result:

ok 100 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

100
22
3 3 3 1 3 2 3 3 3 3 2 2 3 3 1 2 1 2 3 2 3 1
3
10 1 8
11
1 3 2 1 3 3 1 1 1 1 1
3
3 5 13
21
3 1 2 3 2 1 2 1 3 2 2 1 1 1 1 3 2 3 2 3 2
4
1 5 7 10
8
2 1 3 3 2 2 2 2
3
8 11 8
4
2 1 1 2
2
12 8
26
1 2 3 3 1 2 2 2 2 1 3 1 3 2 1 2 1 3 2 1 1 3 2 3 3 2
4
8 6 5 13
30
1 1 3 2 2 1 2 3 1 3 3 2 3 2 2 3 1 2 3...

output:

8
13
12
13
13
17
11
7
6
23
5
5
12
20
2
22
9
10
3
4
22
12
10
5
9
5
11
17
1
20
9
26
8
13
14
10
13
9
17
5
6
11
17
17
18
16
5
19
8
2
13
20
9
8
19
14
16
12
20
19
8
24
7
16
8
5
4
21
1
4
8
9
10
15
7
11
10
2
6
3
4
18
26
8
9
8
11
3
8
6
9
7
20
2
10
22
16
20
14
13

result:

ok 100 lines

Test #4:

score: 0
Accepted
time: 15ms
memory: 5760kb

input:

100
773
2 3 3 2 1 1 1 3 1 3 2 3 2 2 2 2 1 3 3 3 2 3 3 2 2 3 2 1 1 1 3 2 1 1 2 1 2 3 3 3 1 1 3 2 1 3 1 2 3 1 1 1 3 3 1 2 1 3 2 2 3 3 2 3 3 1 3 1 2 3 3 3 2 3 2 1 3 2 3 3 2 2 2 2 3 2 3 1 2 3 2 1 1 1 1 2 2 3 1 2 1 2 2 1 2 3 3 2 2 3 1 3 2 1 2 1 3 3 2 2 3 3 3 1 2 2 3 1 1 3 1 3 3 3 1 3 3 1 1 2 3 2 3 2 2 3 ...

output:

141465623985
146640177725
193302027436
185725363449
27377351959
26962096046
122965020242
164575549427
134405124981
142123242931
239651450114
203676837595
215746363813
176133012841
126667756527
14661286739
153111144139
53633915881
14813690750
194934023573
28317268803
133277272607
239614512471
1786238...

result:

ok 100 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 6636kb

input:

1
45105
3 1 2 1 1 1 1 2 1 3 3 2 1 1 1 3 3 2 2 1 2 1 2 1 3 1 1 3 3 1 3 1 3 3 2 2 1 1 1 1 1 2 2 2 3 3 1 3 2 1 2 2 1 1 2 2 2 3 1 1 3 1 3 3 3 3 2 2 1 3 3 2 1 1 1 1 2 3 1 1 3 1 1 2 2 1 1 2 2 1 3 2 2 3 2 1 3 2 3 3 2 3 2 2 3 2 1 3 1 1 1 3 2 1 1 3 2 2 3 3 1 3 3 3 2 1 3 1 3 3 3 1 3 2 3 2 3 3 3 2 1 1 1 2 1 3 ...

output:

52702719862

result:

ok single line: '52702719862'

Test #6:

score: 0
Accepted
time: 3ms
memory: 5248kb

input:

1
58785
3 2 2 2 2 2 1 1 1 2 1 2 1 1 3 2 1 2 1 2 2 1 1 3 1 3 2 2 2 2 2 2 2 1 1 2 2 3 3 3 2 1 2 3 3 1 3 3 2 1 1 3 3 3 2 1 3 3 1 2 2 1 1 1 2 3 3 1 3 2 1 1 2 2 3 3 1 1 2 2 2 2 1 3 2 2 3 2 3 2 2 3 2 3 1 1 1 1 2 3 1 1 2 2 3 3 3 2 1 1 1 3 1 2 1 1 1 3 2 2 3 1 2 2 3 2 2 2 1 3 3 1 1 3 1 3 3 1 1 3 3 2 1 2 2 1 ...

output:

203100926

result:

ok single line: '203100926'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

10
9
3 3 3 1 1 3 2 1 2
5
6 10 4 3 3
8
3 2 2 2 1 3 3 1
3
7 6 1
6
1 3 2 1 2 3
5
1 9 3 6 3
8
2 1 3 1 3 1 2 3
4
10 4 4 10
3
3 3 1
3
4 4 3
6
3 2 3 3 3 1
1
6
7
3 2 1 1 1 3 1
5
7 4 4 8 7
3
2 2 3
5
5 1 6 8 6
1
3
3
9 10 1
10
3 3 3 1 3 3 3 3 3 1
1
6

output:

12
7
12
15
5
3
17
12
8
2

result:

ok 10 lines