比赛 |
“Asm.Def战记之拉格朗日点”杯 |
评测结果 |
AAAAAAAAAA |
题目名称 |
Asm.Def的微小贡献 |
最终得分 |
100 |
用户昵称 |
前鬼后鬼的守护 |
运行时间 |
0.069 s |
代码语言 |
C++ |
内存使用 |
0.33 MiB |
提交时间 |
2015-11-04 11:47:09 |
显示代码纯文本
#include<cstdio>
#include<cstdlib>
#include<algorithm>
typedef long long ll;
inline ll read(){
ll x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x;
}
int n,cnt;
ll enu[30];
void enume(){
for(int i=0;i<n;i++)enu[i]=read();
for(int S=1,SS=1<<n;S<SS;S++){
ll sumx=0;for(int i=0;i<n;i++)if((S>>i)&1)sumx^=enu[i];
if(sumx==0){
for(int i=0;i<n;i++)if((S>>i)&1)cnt++;printf("%d\n",cnt);
for(int i=0;i<n;i++)if((S>>i)&1)printf("%d ",i+1);
break;
}
}
}
int A[100][100],x[100],P[100];
inline void swap(int& a,int& b){a=a^b,b=a^b,a=a^b;}
int ans[100],tot;
void dfs(int k){
if(!k){
if(cnt){
printf("%d\n",cnt);
for(int i=1;i<=n;i++)if(x[i])ans[tot++]=P[i];
std::sort(ans,ans+tot);
for(int i=0;i<tot;i++)printf("%d ",ans[i]);
exit(0);
}
return;
}
if(A[k][k]){
x[k]=0;
for(int j=k+1;j<=n;j++)
x[k]^=A[k][j]&x[j];
cnt+=x[k];
dfs(k-1);
cnt-=x[k];
}
else{int t=0;
for(int j=k+1;j<=n;j++)t^=A[k][j]&x[j];
if(t!=0)return;
x[k]=0;dfs(k-1);
x[k]=1,cnt++,dfs(k-1),cnt--;
}
}
void gauss(){if(n>=61)n=61;
for(int j=1;j<=n;j++){
ll x=read();P[j]=j;
for(int i=1;i<=61;i++)
if(x>=(1LL<<(i-1))&&(x>>(i-1)&1))
A[i][j]=1;
}n=61;
for(int k=1;k<=n;k++){int _k;
for(_k=k;!A[_k][k]&&_k<=n;_k++);
if(_k>n)continue;
if(_k!=k){
for(int j=k;j<=n;j++)
swap(A[k][j],A[_k][j]);
}
for(int i=k+1;i<=n;i++)if(A[i][k])
for(int j=k;j<=n;j++)
A[i][j]^=A[k][j];
}
dfs(n);
}
int main(){
freopen("asm_contribute.in","r",stdin);
freopen("asm_contribute.out","w",stdout);
n=read();
if(n<=20)enume();
else gauss();
return 0;
}