QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #127233 | #6632. Minimize Median | 45645A# | WA | 37ms | 13620kb | C++14 | 1.7kb | 2023-07-19 14:30:19 | 2023-07-19 14:30:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
char ch;
while((ch=getchar())<'0'||ch>'9');
int res=ch-'0';
while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
return res;
}
const int M=1001000;
const int V=1000000;
int prm[100100],tot,pim[M];
void pre()
{
pim[1]=1;
for(int i=2;i<=V;i++)
{
if(!pim[i]) pim[i]=prm[++tot]=i;
for(int j=1,tmp;j<=tot&&(tmp=prm[j]*i)<=V;j++)
{
pim[tmp]=prm[j];
if(i%prm[j]==0) break;
}
}
}
int n,m,K,c[M],a[M];
struct Tree{
int d[M];
inline int lowbit(int x){ return x&-x; }
void pre(){ for(int i=1;i<=m;i++) d[i]=1e9; }
void upt(int x,int v)
{
for(int i=x;i<=m;i+=lowbit(i))
d[i]=min(d[i],v);
}
int qry(int x)
{
int res=1e9;
for(int i=x;i;i-=lowbit(i)) res=min(res,d[i]);
return res;
}
}T;
int nn;
bool check(int x)
{
int sum=0;
for(int i=1;i<=nn;i++)
{
if(a[i]>x)
{
int tmp=a[i]/x+(a[i]%x!=0);
sum+=c[tmp];
if(sum>K) break;
}
}
return sum<=K;
}
int main()
{
pre();
int t=read();
while(t--)
{
n=read();m=read();K=read();
T.pre();nn=(n+1)/2;
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+1+n);
for(int i=1;i<=m;i++) c[i]=read();
c[1]=0;
// for(int i=1;i<=m;i++) T.upt(m+1-i,c[i]);
// for(int i=2;i<=m;i++)
// {
// c[i]=min(c[i],T.qry(m+1-pim[i])+T.qry(m+1-i/pim[i]));
// T.upt(m+1-i,c[i]);
// }
// for(int i=1;i<=m;i++) c[i]=T.qry(m+1-i);
for(int i=m-1;i>=1;i--) c[i]=min(c[i],c[i+1]);
for(int i=2;i<=m;i++)
{
c[i]=min(c[i],c[pim[i]]+c[i/pim[i]]);
for(int j=1;j<i;j++) c[j]=min(c[j],c[i]);
}
int L=1,R=a[nn];
while(L<=R)
{
int mid=L+R>>1;
if(check(mid)) R=mid-1;
else L=mid+1;
}
printf("%d\n",R+1);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 12336kb
input:
3 3 5 0 2 5 2 3 2 4 6 13 3 5 3 2 5 3 3 2 4 6 13 3 5 6 2 5 2 3 2 4 6 13
output:
2 2 1
result:
ok 3 number(s): "2 2 1"
Test #2:
score: -100
Wrong Answer
time: 37ms
memory: 13620kb
input:
100000 5 10 5 3 7 1 10 10 11 6 11 6 1 8 9 1 3 1 5 6 51 2 2 2 5 1 42 61 26 59 100 54 5 10 76 7 5 8 4 7 97 4 44 83 61 45 24 88 44 44 5 8 90 1 1 5 1 3 35 15 53 97 71 83 26 7 5 3 52 1 1 3 1 1 22 6 93 5 6 28 6 6 1 3 1 9 31 2 19 10 27 5 8 31 3 6 2 1 2 32 29 13 7 57 34 9 5 5 6 75 3 3 4 5 4 40 56 38 60 17 3...
output:
1 2 1 1 1 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 2 1 1 1 2 2 1 1 1 1 1 1 1 1 2 4 1 1 1 1 2 1 1 7 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 1 6 3 1 1 1 1 2 1 1 3 1 1 1 1 1 2 1 1 1 1 1 2 2 4 1 1 1 1 1 1 1 2 2 1 2 2 1 1 1 1 1 1 1 1 1 2 1 4 1 1 4 1 2 1 1 1 1 1 1 2 1 1 1 2 3 1 1 1 1 1 1 1 5 1 1 2 1 2 1 1 ...
result:
wrong answer 1st numbers differ - expected: '0', found: '1'