Cod sursa(job #591474)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 24 mai 2011 12:40:37
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 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], vlad[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;
										//idee originala velea alexandru :D
										vlad[1] = a[l1][c1];
										vlad[2] = a[l1][c2] - a[l1][c1];
										vlad[3] = a[l1][n] - a[l1][c2];
										vlad[4] = a[l2][c1] - a[l1][c1];
										vlad[5] = a[l2][c2] - a[l2][c1] - a[l1][c2] + a[l1][c1];
										vlad[6] = a[l2][n] - a[l2][c2] - a[l1][n] + a[l1][c2];
										vlad[7] = a[n][c1] - a[l2][c1];
										vlad[8] = a[n][c2] - a[n][c1] - a[l2][c2] + a[l2][c1];
										vlad[9] = a[n][n] - a[n][c2] - a[l2][n] + a[l2][c2];
										sort (vlad + 1, vlad + 10);
										int var, ok = 1;
										for (var = 1; var <= 9; ++var)
											if (vlad[var] != v[var]){
												ok = 0;
												break ;
											}
										if (ok){
											g << l1 << ' ' << l2 << ' ' << c1 << ' ' << c2 << '\n';
											return 0;
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	
	g.close ();
	return 0;
}