比赛 “Asm.Def战记之拉格朗日点”杯 评测结果 AAAAAAAAAA
题目名称 Asm.Def的微小贡献 最终得分 100
用户昵称 dydxh 运行时间 0.176 s
代码语言 C++ 内存使用 0.31 MiB
提交时间 2015-11-04 11:48:19
显示代码纯文本
  1. /*
  2. Problem:cogs2092;
  3. Language:c++;
  4. by dydxh;
  5. 2015.11.04;
  6. */
  7. #include<iostream>
  8. #include<cstdio>
  9. #include<set>
  10. #include<map>
  11. #include<queue>
  12. #include<algorithm>
  13. #include<cstring>
  14. #include<cmath>
  15. #include<utility>
  16. #include<ctime>
  17. #include<cstdlib>
  18. #include<bitset>
  19. #include<string>
  20. #define ll long long
  21. #define ull unsigned long long
  22. using namespace std;
  23. const int oo=2000000000;
  24. const int maxn=1005;
  25. int n,ans;
  26. bitset<1005> A[70],Rel[70];
  27. bool used[maxn];
  28. ll a[maxn];
  29. inline ll read(){
  30. ll x=0;bool flag=0;char ch=getchar();
  31. while(ch>'9' || ch<'0') {if(ch=='-') flag=1;ch=getchar();}
  32. while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
  33. return flag?-x:x;
  34. }
  35. bool Gauss(int x){
  36. memcpy(A,Rel,sizeof(A));
  37. for(int j=1;j<=63;j++)
  38. if(A[j][x]){
  39. A[j][x]=false;
  40. if(A[j][n+1]==true) A[j][n+1]=false;
  41. else A[j][n+1]=true;
  42. }
  43. for(int j=1;j<=63;j++){
  44. int i=1;
  45. while(i<=n && A[j][i]==false) i++;
  46. if(i>n && A[j][n+1]==true) return false;
  47. else if(i<=n)
  48. for(int k=j+1;k<=63;k++)
  49. if(A[k][i]==true)
  50. A[k]^=A[j];
  51. }
  52. return true;
  53. }
  54. int main()
  55. {
  56. //freopen("cc.in","r",stdin);
  57. freopen("asm_contribute.in","r",stdin);
  58. freopen("asm_contribute.out","w",stdout);
  59. n=read();
  60. for(int i=1;i<=n;i++) a[i]=read();
  61. for(int i=1;i<=n;i++)
  62. for(int j=1;j<=63;j++){
  63. if((a[i]&(1LL<<(j-1))))
  64. Rel[j][i]=true;
  65. else Rel[j][i]=false;
  66. }
  67. for(int i=1;i<=63;i++) Rel[i][n+1]=false;
  68. for(int i=1;i<=n;i++)
  69. if(Gauss(i)){
  70. used[i]=true;
  71. ans++;
  72. for(int j=1;j<=63;j++)
  73. if(Rel[j][i]){
  74. Rel[j][i]=false;
  75. if(Rel[j][n+1]==true) Rel[j][n+1]=false;
  76. else Rel[j][n+1]=true;
  77. }
  78. }
  79. printf("%d\n",ans);
  80. for(int i=1;i<=n;i++)
  81. if(used[i])
  82. printf("%d ",i);
  83. printf("\n");
  84. return 0;
  85. }