Cod sursa(job #990131)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 27 august 2013 15:42:25
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.58 kb
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>

using namespace std;

#define maxn 514

FILE *f = fopen("zone.in","r");
FILE *g = fopen("zone.out","w");

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


void citire(){


    fscanf(f,"%d",&n);
    for( int i = 0; i <= 8; ++i) {
        fscanf(f,"%lld ",&nr[i]);


    }
    sort( nr, nr + 9);


    for( int i = 1; i <= n; ++i)
        for( int j = 1; j <= n; ++j) {
            fscanf(f,"%d ",&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();

    for( int i = 0; i < 8; ++i)
        for( int j = i + 1; j < 9; ++j)
            for( int k = j + 1; k < 9; ++k) {
                long long  new_sum = nr[i] + nr[j] + nr[k];
                my_sums.insert(new_sum);
            }

    for( int i = 1; i < n; ++i)
        for( int j = i + 1; j < n; ++j){
            long long sum1 = sum_par_lin[i];
            long long sum2 = sum_par_lin[j] - sum_par_lin[i];
            long long 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()) {
                lines.push_back( make_pair(i,j));
            }
        }
    for( int i = 1; i < n; ++i)
        for( int j = i + 1; j < n; ++j){
            long long sum1 = sum_par_col[i];
            long long sum2 = sum_par_col[j] - sum_par_col[i];
            long long 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()) {
                columns.push_back( make_pair(i,j));
            }
        }
    random_shuffle(lines.begin(), lines.end());
    random_shuffle( columns.begin(), columns.end());

    for( size_t i = 0; i < lines.size(); ++i)
        for( size_t j = 0; j < columns.size(); ++j) {
            long long 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);
            sums[1] = calc_sum( 1, c1 + 1, l1, c2);
            sums[2] = calc_sum( 1, c2 + 1, l1, n);
            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;
}