Cod sursa(job #972885)

Utilizator marius135Dumitran Adrian Marius marius135 Data 12 iulie 2013 20:39:28
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.48 kb
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
 
using namespace std;
 
#define maxn 514
 
set<int> 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];
int mat[maxn][maxn],nr[maxn];
 
 
void citire(){
 
    cin>>n;
     
    for( int i = 0; i <= 8; ++i)
        cin>>nr[i];
    sort( nr, nr + 9);
    for( int i = 1; i <= n; ++i) 
        for( int j = 1; j <= n; ++j) {
            cin>> 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];
    }
     
     
 
}
 
int 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) {
                int 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){
            int sum1 = sum_par_lin[i];
            int sum2 = sum_par_lin[j] - sum_par_lin[i];
            int 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){
            int sum1 = sum_par_col[i];
            int sum2 = sum_par_col[j] - sum_par_col[i];
            int 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) {
            int 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;
}