Cod sursa(job #374370)

Utilizator titusuTitus C titusu Data 16 decembrie 2009 21:19:05
Problema Piese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
using namespace std;
#include <fstream>
#include <iostream>
#define NN 510
int a[NN][NN], n, m, nrp;
inline int put2(int n){
	//cea mai mare putere a lui 2, <=n
	int p=1;
	while(p<n)
		p<<=1;
	if(p>n)
		p>>=1;
	return p;
}

void fill(int i1,int j1, int i2,int j2,int deep){
	/*for(int i=1;i<=deep;i++)
		cout<<"-";
	cout<<"("<<i1<<" "<<j1<<") ("<<i2<<" "<<j2<<")\n";
	*/
	if(i1>i2 || j1>j2)
		return ;
	int i=i2-i1+1, j=j2-j1+1;
	if(i<=j){
		int p=put2(i);
		if(p<i){
			fill(i1,j1,i2,j1+p-1,deep+1);
			fill(i1,j1+p,i2,j2,deep+1);
		}
		else
		{
			nrp++;
			for(int l=i1;l<=i2;l++)
				for(int c=j1;c<=j1+p-1;c++)
					a[l][c]=nrp;
			fill(i1,j1+p,i2,j2,deep+1);
		}
	}
	else{
		//j<i
		int p=put2(j);
		if(p<j){
			fill(i1,j1,i1+p-1,j2,deep+1);
			fill(i1+p,j1,i2,j2,deep+1);
		}
		else
		{
			nrp++;
			for(int l=i1;l<=i1+p-1;l++)
				for(int c=j1;c<=j2;c++)
					a[l][c]=nrp;
			fill(i1+p,j1,i2,j2,deep+1);
		}
	}
}

int main(){
	ifstream fin("piese.in");
	fin>>n>>m;
	fill(1,1,n,m,0);
	ofstream fout("piese.out");
	fout<<nrp<<endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			fout<<a[i][j]<<" ";
		fout<<endl;
	}
	return 0;
}