2021牛客暑期多校训练营10

H War of Inazuma (Easy Version)

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>

#define fi first
#define se second

#define lowbit(x) (x&-x)

using namespace std;

namespace ae86{
    const int bufl=1<<15;
    char buf[bufl],*s=buf,*t=buf;
    inline int fetch(){
        if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
        return*s++;
    }
    inline int read(){
        int a=0,b=1,c=fetch();
        while(!isdigit(c))b^=c=='-',c=fetch();
        while(isdigit(c))a=a*10+c-48,c=fetch();
        return b?a:-a;
    }
}
using ae86::read;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,double> pid;

const int inf=0x3f3f3f3f;
const ll INF=2e18;
const double eps=1e-8;
const double pi=acos(-1);
const int mod=1e9+7;

int n;
int a[(1<<22)];

int main(){
    cin>>n;
    memset(a,-1,sizeof a);
    int num=ceil(sqrt(n));
    int cnt0,cnt1;
    for(int i=0;i<(1<<n);i++){
        if(a[i]==1){
            cnt1=num;
            cnt0=n-num;
        }
        else{
            cnt0=num;
            cnt1=n-num;
        }
        for(int j=0;j<=n-1;j++){
            int tmp=i^(1<<j);
            if(a[tmp]==1)    cnt1--;
            else if(a[tmp]==0)    cnt0--;
            else{
                if(cnt0){
                    a[tmp]=0;
                    cnt0--;
                }    
                else{
                    a[tmp]=1;
                    cnt1--;
                }
            }
        }
    }
    for(int i=0;i<(1<<n);i++)    printf("%d",a[i]);
}