记录编号	162558	评测结果	AAAAAAAAAA
题目名称	[Vijos 1071] 新年趣事之打牌	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.044 s
提交时间	2015-05-17 19:43:56	内存使用	98.05 MiB

#include <cstdio>

using namespace std;

void print_solution();

int n,known_weight,weight[201],f[500000],temp,ans[201],cs;
bool used[201][500000];

int main()
{
	freopen("bagb.in","r",stdin);
	freopen("bagb.out","w",stdout);
    scanf("%d%d",&known_weight,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&weight[i]);known_weight-=weight[i];
    }known_weight=-known_weight;f[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=known_weight;j>=0;j--){
            if(j>=weight[i]){
                temp=f[j];
                f[j]+=f[j-weight[i]];
                if(temp!=f[j]){
                    used[i][j]=1;
                }
            }
        }
    }
    if(f[known_weight]==0) printf("0");
    else if(f[known_weight]>1) printf("-1");
    else print_solution();
    return 0;
}

void print_solution()
{
    while(n>0){
        if(used[n][known_weight]==1){
            known_weight-=weight[n];
            ans[++cs]=n;
        }
        n--;
    }
    printf("%d",ans[cs]);
    for(int i=cs-1;i>=1;i--){
        printf(" %d",ans[i]);
    }
    return;
}