Cod sursa(job #591458)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 24 mai 2011 12:07:35
Problema Zone Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
# include <fstream>
# include <algorithm>
using namespace std;

ifstream f ("zone.in");
ofstream g ("zone.out");

int n, a[513][513], i, j, k1, k2, v[10], ap[10];

int bs_lin (int lin, int find, int minus){
	int i, cnt = (1 << 9);
	
	for (i = 1; cnt > 0; cnt >>= 1){
		int aux = i + cnt;
		if (aux <= n){
			if (a[lin][aux] - minus <= find) i = aux;
		}
	}
	
	return (a[lin][i] - minus == find ? i : 0);
}

int bs_col (int col, int find, int minus){
	int i, cnt = (1 << 9);
	
	for (i = 1; cnt > 0; cnt >>= 1){
		int aux = i + cnt;
		if (aux <= n){
			if (a[aux][col] - minus <= find) i = aux;
		}
	}
	
	return (a[i][col] - minus == find ? i : 0);
}

int bs_vec (int find){
	int i, cnt = (1 << 3);
	
	for (i = 1; cnt > 0; cnt >>= 1){
		int aux = i + cnt;
		if (v[aux] <= find) i = aux;
	}
	
	return (v[i] == find ? i : 0);
}
int main (){
	f >> n;
	
	for (i = 1; i <= 9; ++i) f >> v[i];
	sort (v + 1, v + 10);
	
	for (i = 1; i <= n; ++i){
		for (j = 1; j <= n; ++j){
			f >> a[i][j];
			a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
		}
	}
	
	for (i = 1; i <= n; ++i){
		for (j = 1; j <= n; ++j){
			int v1 = bs_vec (a[i][j]);
			if (v1){//v1 e pozitia lui a[i][j]
				for (k1 = 1; k1 <= 9; ++k1){
					if (k1 != v1){
						int v2 = bs_lin (i, v[k1], a[i][j]);//v2 e c2
						if (v2){
							for (k2 = 1; k2 <= 9; ++k2){
								if (k2 != k1 && k2 != v1){
									int v3 = bs_col (j, v[k2], a[i][j]);//v3 e l2
									if (v3){
										int l1 = i, c1 = j, l2 = v3, c2 = v2;
										ap[v1] = ap[k1] = ap[k2] = 1;
										int var;
										//zona 3
										var = bs_vec (a[i][n] - a[i][c2]);
										if (ap[var]) continue ;
										ap[var] = 1;
										//zona 5
										var = bs_vec (a[l2][c2] - a[l2][c1] - a[l1][c2] + a[l1][c1]);
										if (ap[var]) continue ;
										ap[var] = 1;
										//zona 6
										var = bs_vec (a[l2][n] - a[l2][c2] - a[l1][n] + a[l1][c2]);
										if (ap[var]) continue ;
										ap[var] = 1;
										//zona 7
										var = bs_vec (a[n][c1] - a[l2][c1]);
										if (ap[var]) continue ;
										ap[var] = 1;
										//zona 8
										var = bs_vec (a[n][c2] - a[n][c1] - a[l2][c2] + a[l2][c1]);
										if (ap[var]) continue ;
										ap[var] = 1;
										//zona 9
										var = bs_vec (a[n][n] - a[n][c2] - a[l2][n] + a[l2][c2]);
										if (ap[var]) continue ;
										ap[var] = 1;
										g << l1 << ' ' << l2 << ' ' << c1 << ' ' << c2 << '\n';
										return 0;
									}
								}
							}
						}
					}
				}
			}
		}
	}
	
	g.close ();
	return 0;
}