Cod sursa(job #1326650)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 25 ianuarie 2015 19:43:45
Problema Zone Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.34 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n, i, j, p, u, mid, l1, l2, c1, c2, ii1, ii2, jj1, jj2, ok, k;
int a[515][515], b[515][515], s[10], s1[10];
ifstream fin("zone.in");
ofstream fout("zone.out");
int suma(int x, int y, int z, int t){
	return b[z][t] - b[x-1][t] - b[z][y-1] + b[x-1][y-1]; 
}
int main(){
	fin>> n;
	for(i = 1; i <= 9; i++){
		fin>> s[i];
	}
	sort(s + 1, s + 10);
	l1 = l2 = c1 = c2 = 1000;
	for(i = 1; i <= n; i++){
		for(j = 1; j <= n; j++){
			fin>> a[i][j];
			b[i][j] = a[i][j] + b[i-1][j] + b[i][j-1] - b[i-1][j-1];
		}
	}
	for(i = 1; i <= 9; i++){
		for(ii1 = 1; ii1 < n - 1; ii1++){
			p = 1;
			u = n - 2;
			while(p <= u){
				mid = (p + u) / 2;
				if(s[i] == b[ii1][mid]){
					break;
				}
				else{
					if(s[i] > b[ii1][mid]){
						u = mid - 1;
					}
					else{
						p = mid + 1;
					}
				}
			}
			if(p > u){
				continue;
			}
			jj1 = mid;
			for(j = 1; j <= 9; j++){
				if(i != j){
					p = jj1 + 1;
					u = n - 1;
					while(p <= u){
						mid = (p + u) / 2;
						if(s[j] == b[ii1][mid] - b[ii1][jj1]){
							break;
						}
						else{
							if(s[j] > b[ii1][mid] - b[ii1][jj1]){
								u = mid - 1;
							}
							else{
								p = mid + 1;
							}
						}
					}
					if(p > u){
						continue;
					}
					jj2 = mid;
					for(k = 1; k <= 9; k++){
						if(k != i && k != j){
							p = ii1 + 1;
							u = n - 1;
							while(p <= u){
								mid = (p + u) / 2;
								if(s[k] == b[mid][jj1] - b[ii1][jj1]){
									break;
								}
								else{
									if(s[k] > b[mid][jj1] - b[ii1][jj1]){
										u = mid - 1;
									}
									else{
										p = mid + 1;
									}
								}
							}
							if(p > u){
								continue;
							}
							ii2 = mid;
							s1[1]=suma(1, 1, ii1, jj1);
                            s1[2]=suma(ii1 + 1, 1, ii2, jj1);
                            s1[3]=suma(ii2 + 1, 1, n, jj1);
                            s1[4]=suma(1, jj1+1, ii1, jj2);
                            s1[5]=suma(ii1 + 1, jj1 + 1, ii2, jj2);
                            s1[6]=suma(ii2 + 1, jj1+1, n, jj2);
                            s1[7]=suma(1, jj2 + 1, ii1, n);
                            s1[8]=suma(ii1 + 1 ,jj2 + 1, ii2, n);
                            s1[9]=suma(ii2 + 1,jj2 + 1, n, n);
							sort(s1 + 1, s1 + 10);
							ok = 1;
							for(int ii = 1; ii <= 9; ii++){
								if(s1[ii] != s[ii]){
									ok = 0;
									break;
								}
							}
							if(ok == 1){
								if(ii1 < l1){
									l1 = ii1;
									c1 = jj1;
									l2 = ii2;
									c2 = jj2;
								}
								else{
									if(ii1 == l1){
										if(c1 > jj1){
											l1 = ii1;
											c1 = jj1;
											l2 = ii2;
											c2 = jj2;
										}
										else{
											if(c1 == jj1){
												if(l2 > ii2){
													l1 = ii1;
													c1 = jj1;
													l2 = ii2;
													c2 = jj2;
												}
												else{
													if(l2 == ii2){
														if(c2 > jj2){
															l1 = ii1;
															c1 = jj1;
															l2 = ii2;
															c2 = jj2;
														}
													}
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	fout<< l1 <<" "<< l2 <<" "<< c1 <<" "<< c2 <<"\n";
	return 0;
}