Cod sursa(job #972887)

Utilizator marius135Dumitran Adrian Marius marius135 Data 12 iulie 2013 20:41:01
Problema Zone Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.14 kb
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<bitset>
#include<map>

using namespace std;

#define maxn 514

map <int,int> my_sums;
vector < pair<int, int> > lines, columns;
long long mat[maxn][maxn], sum_lin[maxn], sum_col[maxn], sum_par_lin[maxn], sum_par_col[maxn];
int n;
long long sum_mat[maxn][maxn], nr[maxn];

vector< bitset<9> > indici;
int options = -1;
set <int> sume;


void citire(){

	cin>>n;
	
	for( int i = 0; i <= 8; ++i) {
		cin>>nr[i];
		sume.insert(nr[i]);
		
	}
	sort( nr, nr + 9);
	
		
	for( int i = 1; i <= n; ++i) 
		for( int j = 1; j <= n; ++j) {
			cin>> mat[i][j];
			sum_lin[i] += mat[i][j];
			sum_col[j] += mat[i][j];
			sum_mat[i][j] = sum_mat[i][j-1] + sum_col[j];
		}
	
	for( int i = 1; i <= n; ++i) {
		sum_par_lin[i] = sum_par_lin[i-1] + sum_lin[i];
		sum_par_col[i] = sum_par_col[i-1] + sum_col[i];
	}
	
	

}

long long calc_sum( int x1, int y1, int x2, int y2){
	
	return sum_mat[x1-1][y1-1] + sum_mat[x2][y2] - sum_mat[ x1-1][y2] - sum_mat[ x2][y1-1];
}

int main() {
	
	freopen("zone.in", "r", stdin);
	//freopen("zone.out", "w", stdout);
	
	citire();
	
	return 0;
	
	for( int i = 0; i < 8; ++i)
		for( int j = i + 1; j < 9; ++j)
			for( int k = j + 1; k < 9; ++k) {
				int new_sum = nr[i] + nr[j] + nr[k];
				if( my_sums.find( new_sum) == my_sums.end()) {
					my_sums[new_sum] = ++options;
					bitset <9> bla;
					bla[i] = bla[j] = bla[k] = true;
					//cout<<bla<<endl;
					indici.push_back(bla);
				}
				else {
					indici[my_sums[new_sum]][i] = indici[my_sums[new_sum]][j] = indici[my_sums[new_sum]][k] = true;
				}
			}
	
	
	for( int i = 1; i < n; ++i)
		for( int j = i + 1; j < n; ++j){
			int sum1 = sum_par_lin[i];
			int sum2 = sum_par_lin[j] - sum_par_lin[i];
			int sum3 = sum_par_lin[n] - sum_par_lin[j];
			if( my_sums.find(sum1) != my_sums.end() && my_sums.find(sum2) != my_sums.end() && my_sums.find(sum3) != my_sums.end()) {
				bitset <9> test;
				cout<<indici[my_sums[sum1]]<<" "<<indici[my_sums[sum2]]<<" "<<indici[my_sums[sum3]]<<endl;
				test = ( indici[my_sums[sum1]] | indici[my_sums[sum2]] | indici[my_sums[sum3]]);
				
				int ok = 1;
				for( int k = 0; k < 9; ++k)
					if( test[k] == 0) {
						ok = 0;
						break;
					}
				if( ok == 1)
					lines.push_back( make_pair(i,j));
			}
		}
	for( int i = 1; i < n; ++i)
		for( int j = i + 1; j < n; ++j){
			int sum1 = sum_par_col[i];
			int sum2 = sum_par_col[j] - sum_par_col[i];
			int sum3 = sum_par_col[n] - sum_par_col[j];
			if( my_sums.find(sum1) != my_sums.end() && my_sums.find(sum2) != my_sums.end() && my_sums.find(sum3) != my_sums.end()) {
				bitset <9> test;
				test = ( indici[my_sums[sum1]] | indici[my_sums[sum2]] | indici[my_sums[sum3]]);
				
				int ok = 1;
				
				for( int k = 0; k < 9; ++k)
					if( test[k] == 0) {
						ok = 0;
						break;
					}
				if( ok == 1)
					columns.push_back( make_pair(i,j));
			}
		}
	random_shuffle(lines.begin(), lines.end());
	random_shuffle( columns.begin(), columns.end());
	
	cout<<lines.size()<<endl<<columns.size()<<endl;
	
	for( size_t i = 0; i < lines.size(); ++i)
		for( size_t j = 0; j < columns.size(); ++j) {
			int sums[9];
			int l1 = lines[i].first, l2 = lines[i].second;
			int c1 = columns[j].first, c2 = columns[j].second;
			
			sums[0] = calc_sum( 1, 1, l1, c1);
			if( sume.find(sums[0]) == sume.end())
				break;
			sums[1] = calc_sum( 1, c1 + 1, l1, c2);
			if( sume.find(sums[1]) == sume.end())
				break;
			
			sums[2] = calc_sum( 1, c2 + 1, l1, n);
			if( sume.find(sums[2]) == sume.end())
				break;
			
			sums[3] = calc_sum( l1 + 1, 1, l2, c1);
			sums[4] = calc_sum( l1 + 1, c1 + 1, l2, c2);
			sums[5] = calc_sum( l1 + 1, c2 + 1, l2, n);
			sums[6] = calc_sum( l2 + 1, 1, n, c1);
			sums[7] = calc_sum( l2 + 1, c1 + 1, n, c2);
			sums[8] = calc_sum( l2 + 1, c2 + 1, n, n);
			sort( sums, sums + 9);
			int ok = 1;
			for( int i = 0; i <= 8; ++i)
				if( sums[i] != nr[i]) {
					ok = 0;
					break;
				}
			if( ok == 1) {
				cout<<l1<<" "<<l2<<" "<<c1<<" "<<c2<<endl;
				return 0;
			}
		}
	
	return 0;
}