QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#641613#8790. First BillionwallcrackWA 0ms3876kbC++201.4kb2024-10-14 21:37:542024-10-14 21:37:55

Judging History

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

  • [2024-10-14 21:37:55]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3876kb
  • [2024-10-14 21:37:54]
  • 提交

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]