比赛 “Asm.Def战记之拉格朗日点”杯 评测结果 AAAAATTATT
题目名称 Asm.Def的微小贡献 最终得分 60
用户昵称 starli 运行时间 16.986 s
代码语言 C++ 内存使用 0.36 MiB
提交时间 2015-11-04 11:03:18
显示代码纯文本
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5. long long chosen[1010],n,sum[1010];
  6. bool vis[1010];
  7. struct aa{long long a,id;}A[1010];
  8.  
  9. vector<aa> ha[2000];
  10.  
  11. int hash_find(long long x){
  12. long long tmp=x%1047;
  13. int s=ha[tmp].size();
  14. for(int i=0;i<s;i++) if(ha[tmp][i].a==x && !vis[ha[tmp][i].id]) return ha[tmp][i].id;
  15. return 0;
  16. }
  17.  
  18. void hash_insert(aa x){
  19. if(hash_find(x.a) && hash_find(x.a)==x.id) return;
  20. long long tmp=(x.a)%1047;
  21. ha[tmp].push_back(x);
  22. }
  23.  
  24. void dfs(int a,int pre,long long now,int maxd){
  25. if(a>1 && now==0) {
  26. printf("%d\n",a-1);
  27. for(int i=1;i<a;i++) printf("%lld ",chosen[i]);
  28. exit(0);
  29. }
  30. if(a>maxd) return;
  31. if(hash_find(now)) {
  32. int i=hash_find(now);
  33. if(!vis[i]){
  34. chosen[a]=A[i].id;vis[i]=true;
  35. dfs(a+1,0,now^A[i].a,maxd);
  36. chosen[a]=0;vis[i]=false;
  37. }
  38. }
  39. for(int i=pre+1;i<=n;i++) {
  40. if(!vis[i]){
  41. chosen[a]=A[i].id;vis[i]=true;
  42. dfs(a+1,i,now^A[i].a,maxd);
  43. chosen[a]=0;vis[i]=false;
  44. }
  45. }
  46. }
  47.  
  48. int main(){
  49. freopen("asm_contribute.in","r",stdin);freopen("asm_contribute.out","w",stdout);
  50. scanf("%lld",&n);
  51. 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]);
  52. for(int i=1;i<=n;i++) if(!sum[i]) {
  53. printf("%d\n",i) ;
  54. for(int j=1;j<=i;j++) printf("%d ",j);
  55. exit(0);
  56. }
  57. for(int i=1;i<=n;i++) dfs(1,0,0,i);
  58. return 0;
  59.  
  60. }