Submission #31596691

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

const double pi = acos(-1.0);
const int N = 262144;

vector<int> lr(N*4+10,-1); // -1 unset 0:01, 1:10

int a[N+10];

int n;
bool build(int pos,int val,int idx = 1,int pwr = 0){
  if(pwr == n)return true;
  int direction = pos%2;
  int v = direction != val%2;
  if(lr[idx] != -1 && lr[idx] != v){
    return false;
  }
  lr[idx] = v;
  return build(pos/2,val/2,idx*2+direction,pwr+1);
}

int xorcache[20] = {0}; // 不要实际的xor, 修改代价大

vector<int>ans;

void fix(int val){
  // printf("Fix %d\n",val);
  int x = 0;
  {
    int pwr = n-1;
    int v = val;
    while(pwr--){
      if(v%2 == (lr[v/2] ^ xorcache[pwr])){
        x |= (1<<(pwr));
      }
      v/=2;
    }
  }
  // printf("xor %d\n",x);
  if(x){
    ans.push_back(x);
    rep(pwr,0,n){
      if((1<<pwr) & x)xorcache[pwr]^=1; // 标记
    }
  }
  // printf("+1\n");
  {
    int idx = 1;
    rep(pwr,0,n){
      if(lr[idx]^xorcache[pwr]){
        idx=idx*2;
      }else{
        idx=idx*2+1;
      }
      lr[idx/2] ^= 1;
    }
  }
  ans.push_back(-1);
}


int main(){
  cin>>n;
  rep(i,0,(1<<n)){
    scanf("%d",a+i);
  }
  rep(i,0,(1<<n)){
    int r = build(i,a[i]);
    if(!r){
      printf("No\n");
      return 0;
    }
  }
  // rep(i,1,8){
  //   printf("lr[%lld]= %d\n",i,lr[i]);
  // }
  rep(i,(1<<(n-1)),(1<<n)){
    if(lr[i] == 0)continue;
    fix(i);
  }
  int x = 0;
  rep(pwr,0,n){
    if(lr[1<<pwr] ^ xorcache[pwr]){
      x |= 1<<pwr;
      xorcache[pwr] ^= 1;
    }
  }
  if(x){
    ans.push_back(x);
  }
  rep(pwr,0,n){
    rep(i,(1<<pwr),(1<<(pwr+1))){
      if(lr[i]^xorcache[pwr]){
        printf("No\n");
        return 0;
      }
    }
  }
  printf("Yes\n");
  printf("%d\n",(int)ans.size());
  rep(i,0,(int)ans.size()){
    printf("%d ",ans[i]);
  }
  printf("\n");
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:72:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   72 |     scanf("%d",a+i);
      |     ~~~~~^~~~~~~~~~

Judge Result