QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#641613 | #8790. First Billion | wallcrack | WA | 0ms | 3876kb | C++20 | 1.4kb | 2024-10-14 21:37:54 | 2024-10-14 21:37:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int B=36,N=100+10;
typedef pair<int,bitset<N>> Pib;
int n,b;
Pib a[N],c[B+10];
mt19937 rnd(time(0));
void operator +=(Pib &x,Pib &y)
{
x.first+=y.first;
x.second|=y.second;
}
bool cmp(Pib &x,Pib &y)
{
return x.first<y.first;
}
Pib solve()
{
vector<Pib> p1,p2;
for(int i=1;i<=b;i++)
if(i<=b/2)p1.push_back(c[i]);
else p2.push_back(c[i]);
vector<Pib> archive;
for(int i=0;i<(1<<p1.size());i++)
{
Pib cur;
for(int j=0;j<p1.size();j++)
if(i&(1<<j))cur+=p1[j];
archive.push_back(cur);
}
sort(archive.begin(),archive.end(),cmp);
for(int i=0;i<(1<<p2.size());i++)
{
Pib cur;
for(int j=0;j<p2.size();j++)
if(i&(1<<j))cur+=p2[j];
int l=0,r=archive.size()-1,mid;
while(l<r)
{
mid=(l+r+1)>>1;
if(cur.first+archive[mid].first<=1e9)l=mid;
else r=mid-1;
}
auto res=cur;
res+=archive[l];
if(res.first==1e9)return res;
}
Pib any;
return any;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].first;
a[i].second[i]=1;
}
Pib ans;
do
{
shuffle(a+1,a+1+n,rnd);
b=min(n,B);
for(int i=1;i<=b;i++)
{
int p=1,minv=1e9;
for(int j=1;j<=b;j++)
if(c[j].first<minv)
p=j,minv=c[j].first;
c[p]+=a[i];
}
ans=solve();
cout<<ans.first<<endl;
}while(ans.first!=1e9);
cout<<ans.second.count()<<" ";
for(int i=1;i<=n;i++)
if(ans.second[i])cout<<i<<" ";
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3876kb
input:
10 386413329 88494216 245947398 316438989 192751270 204627269 65749456 3938400 150458676 345180997
output:
1000000000 5 1 5 6 7 9
result:
wrong answer Integer parameter [name=failed] equals to 1000000000, violates the range [0, 10]