Pagini recente » Cod sursa (job #2683560) | Cod sursa (job #202833) | Cod sursa (job #1648009) | Cod sursa (job #1602489) | Cod sursa (job #2078344)
#include <fstream>
#include <bitset>
#define DIM 515
using namespace std;
ifstream fin ("zone.in");
ofstream fout ("zone.out");
int n,i,j,a[DIM][DIM],s[DIM][DIM],v[11],x[11],OK,s1,s2,s3;
bitset <10> f;
int verif (int sum){
for (int i=1;i<=9;i++){
if (v[i] == sum && f[i] == 0){
f[i] = 1;
return 1;
}
}
return 0;
}
int main (){
fin>>n;
for (i=1;i<=9;i++)
fin>>v[i];
for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
fin>>a[i][j];
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
}
//back (1);
int c1,c2,l1,l2,mid,st,dr;
///
for (s1=1;s1<=9;s1++){
for (int i=1;i<n-1;i++){
/// cautam binar coloana 1
int ok = 0;
st = 1;
dr = n-2;
while (st <= dr){
mid = (st+dr)/2;
if (s[i][mid] == v[s1]){
c1 = mid;
break;
}
else{
if (s[i][mid] < v[s1])
st = mid+1;
else
dr = mid-1;
}
}
if (st > dr){ /// nu am putut fixa coloana 1
ok = 1;
continue;
}
//if (st <= dr){/// inseamna ca am gasit suma 1
// int c1 = mid;
/// cautam binar coloana 2
for (s2=1;s2<=9;s2++){
if (s1 == s2)
continue;
st = c1+1;
dr = n-1;
while (st <=dr){
mid = (st+dr)/2;
if (s[i][mid] - s[i][c1] == v[s2])
break;
else
if (s[i][mid] - s[i][c1] < v[s2])
st = mid+1;
else
dr = mid-1;
}
if (st > dr){
ok = 1;
continue;
}
/* else{
if (s[i][n] - s[i][mid] == v[x[3]]){ //*************************
/// am putut fixa coloana a doua
c2 = mid;
}
else{
ok = 1;
continue;
}
}*/
c2 = mid;
for (s3=1;s3<=9;s3++){ /// fixam suma a treia
if (s2 == s3 || s1 == s3)
continue;
/// cautam binar linia a doua
st = i+1;
dr = n-1;
while (st <= dr){
mid = (st+dr)/2;
int sum = s[mid][c1] - s[i][c1];
if (sum == v[s3]){
l2 = mid;
break;
}
else{
if (sum < v[s3])
st = mid+1;
else
dr = mid-1;
}
}
if (st > dr){ /// nu am putut fixa linia 2
ok = 1;
continue;
}
//int l2 = mid;
int sum3 = s[i][n] - s[i][c2];
int sum5 = s[mid][c2] - s[mid][c1] - s[i][c2] + s[i][c1];
int sum6 = s[mid][n] - s[mid][c2] - s[i][n] + s[i][c2];
int sum7 = s[n][c1] - s[l2][c1];
int sum8 = s[n][c2] - s[n][c1] - s[l2][c2] + s[l2][c1];
int sum9 = s[n][n] - s[n][c2] - s[l2][n] + s[l2][c2];
f.reset();
f[s1] = f[s2] = f[s3] = 1;
if (verif(sum3) && verif (sum5) && verif (sum6) && verif (sum7) && verif(sum8) && verif (sum9)){
/// am gasit o solutie;
fout<<i<<" "<<l2<<" "<<c1<<" "<<c2;
return 0;
}
// if (!(sum5 == v[x[5]] && sum6 == v[x[6]] && sum7 == v[x[7]] && sum8 == v[x[8]] && sum9 == v[x[9]]) ){
// ok = 1;
// continue;
// }
}
}
}
}
return 0;
}