QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#207641 | #6769. Monster Hunter | veg# | AC ✓ | 15ms | 6636kb | C++23 | 2.3kb | 2023-10-08 18:17:10 | 2023-10-08 18:17:10 |
Judging History
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