比赛 “Asm.Def战记之拉格朗日点”杯 评测结果 AAAAATTATT
题目名称 Asm.Def的微小贡献 最终得分 60
用户昵称 starli 运行时间 16.986 s
代码语言 C++ 内存使用 0.36 MiB
提交时间 2015-11-04 11:03:18
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
long long chosen[1010],n,sum[1010];
bool vis[1010];
struct aa{long long a,id;}A[1010];

vector<aa> ha[2000];

int hash_find(long long x){
    long long tmp=x%1047;
    int s=ha[tmp].size();
    for(int i=0;i<s;i++) if(ha[tmp][i].a==x && !vis[ha[tmp][i].id]) return ha[tmp][i].id;
    return 0;
}

void hash_insert(aa x){
    if(hash_find(x.a) && hash_find(x.a)==x.id) return;
    long long tmp=(x.a)%1047;
    ha[tmp].push_back(x);
}

void dfs(int a,int pre,long long now,int maxd){
    if(a>1 && now==0) {
        printf("%d\n",a-1);
        for(int i=1;i<a;i++) printf("%lld ",chosen[i]); 
        exit(0);
    }
    if(a>maxd) return;
    if(hash_find(now)) {
        int i=hash_find(now);
        if(!vis[i]){
            chosen[a]=A[i].id;vis[i]=true;
            dfs(a+1,0,now^A[i].a,maxd);
            chosen[a]=0;vis[i]=false;
        }
    }
    for(int i=pre+1;i<=n;i++) {
        if(!vis[i]){
            chosen[a]=A[i].id;vis[i]=true;
            dfs(a+1,i,now^A[i].a,maxd);
            chosen[a]=0;vis[i]=false;
        }
    }
}

int main(){
    freopen("asm_contribute.in","r",stdin);freopen("asm_contribute.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&A[i].a),A[i].id=i,sum[i]=sum[i-1]^A[i].a,hash_insert(A[i]);
    for(int i=1;i<=n;i++) if(!sum[i]) {
        printf("%d\n",i) ;
        for(int j=1;j<=i;j++) printf("%d ",j);
        exit(0);
    }
    for(int i=1;i<=n;i++) dfs(1,0,0,i);
    return 0;

}