Cod sursa(job #507704)

Utilizator AndreyPAndrei Poenaru AndreyP Data 6 decembrie 2010 17:11:13
Problema Oras Scor 20
Compilator cpp Status done
Runda selectie-vianu-2011 Marime 2.37 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 210
#define pii pair< int,int >
#define fs first
#define sc second
#define mp make_pair

int n;
char a[N][N];
pii g[N];
int lung[N];
int nrg;

inline bool put3(int k) {
	while(k>1) {
		if(k%3==0) {
			k /= 3;
			continue;
		}
		return false;
	}
	return true;
}

void rezolva3(int pr,int ul) {
	if(pr==ul)
		return;
	int lun = (ul-pr+1)/3;
	int s1 = pr;
	int s2 = pr+lun;
	int s3 = s2+lun;
	
	for(int i=s1; i<s2; ++i) {
		for(int j=s2; j<s3; ++j)
			a[i][j] = '1';
	}
	
	for(int i=s2; i<s3; ++i) {
		for(int j=s3; j<=ul; ++j)
			a[i][j] = '1';
	}
	
	for(int i=s3; i<=ul; ++i) {
		for(int j=s1; j<s2; ++j)
			a[i][j] = '1';
	}
	
	rezolva3(s1,s2-1);
	rezolva3(s2,s3-1);
	rezolva3(s3,ul);
}

inline void scrie() {
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j)
			fputc(a[i][j],stdout);
		fputc('\n',stdout);
	}
}

inline void descom() {
	int n1 = n;
	int p=1;
	int pr=1;
	int r;
	
	while(n1>0) {
		r = n1%3;
		for(int i=0; i<r; ++i) {
			++nrg;
			g[nrg].fs = pr;
			g[nrg].sc = pr+p-1;
			pr += p;
		}
		p *= 3;
	}
}

int main() {
	freopen("oras.in","r",stdin);
	freopen("oras.out","w",stdout);
	
	scanf("%d",&n);
	
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j)
			a[i][j] = '0';
	}
	
	if(put3(n)) {
		rezolva3(1,n);
		scrie();
		return 0;
	}
	
	if(n==5) {
		fputs("00001\n10010\n11000\n10100\n01110\n",stdout);
		return 0;
	}
	
	if(n==6) {
		fputs("000011\n100101\n110000\n101000\n011100\n001110\n",stdout);
		return 0;
	}
	
	if(n==7) {
		fputs("0000001\n1000010\n1100100\n1110000\n1101000\n1011100\n0111110\n",stdout);
		return 0;
	}
	
	if(n==8) {
		fputs("00000011\n10000101\n11001000\n11100000\n11010000\n10111000\n01111100\n00111110\n",stdout);
		return 0;
	}
	
	descom();
	if(nrg%2==0)
		printf("-1\n");
	
	for(int i=1; i<=nrg; ++i)
		rezolva3(g[i].fs,g[i].sc);
	int pr=1,ul=g[1].sc;
	
	for(int k=2; k<nrg; k+=2) {
		for(int i=pr; i<=ul; ++i) {
			for(int j=g[k].fs; j<=g[k].sc; ++j) {
				a[i][j] = '1';
			}
		}
		
		for(int i=g[k].fs; i<=g[k].sc; ++i) {
			for(int j=g[k+1].fs; j<=g[k+1].sc; ++j) {
				a[i][j] = '1';
			}
		}
		
		for(int i=g[k+1].fs; i<=g[k+1].sc; ++i) {
			for(int j=pr; j<=ul; ++j) {
				a[i][j] = '1';
			}
		}
		ul = g[k+1].sc;
	}
	
	printf("-1\n");
	
	return 0;
}