Cod sursa(job #2477261)

Utilizator flibiaVisanu Cristian flibia Data 19 octombrie 2019 21:46:19
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.09 kb
#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long 

using namespace std;

	
#define dim 10001
char buff[dim];
int pos = 0;
 
void read(ll &nr) {
	nr = 0;
	while ((buff[pos] < '0' || buff[pos] > '9') && buff[pos] != '-')
		if (++pos == dim) 
			fread(buff, 1, dim, stdin), pos = 0;
	while (buff[pos] >= '0' && buff[pos] <= '9') {
		nr = 10 * nr + buff[pos] - '0';
		if (++pos == dim) 
			fread(buff, 1, dim, stdin), pos = 0;
	}
}

ll n, v[10], a[515][515], dp[2][515][515];
vector<pair<int, int> > can[2][10];
vector<ll> fx, aux;
vector<pair<pair<int, int>, pair<int, int> > > sol;

int main() {
    freopen("zone.in", "r", stdin);
	freopen("zone.out", "w", stdout);
    read(n);
    for (int i = 1; i <= 9; i++) 
        read(v[i]), fx.push_back(v[i]);

    sort(v + 1, v + 10);
    sort(fx.begin(), fx.end());

    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++)
            read(a[i][j]);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dp[0][i][j] = a[i][j] + dp[0][i - 1][j] + dp[0][i][j - 1] - dp[0][i - 1][j - 1];

    for (int i = n; i > 0; i--)
        for (int j = n; j > 0; j--)
            dp[1][i][j] = a[i][j] + dp[1][i + 1][j] + dp[1][i][j + 1] - dp[1][i + 1][j + 1];
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) 
            for (int k = 1; k <= 9; k++) {
                if (dp[0][i][j] == v[k])
                    can[0][k].push_back({i, j});
                if (dp[1][i][j] == v[k])   
                    can[1][k].push_back({i, j});
            }

    for (int k1 = 1; k1 <= 9; k1++)
        for (int k2 = 1; k2 <= 9; k2++) {
            if (k1 == k2)
                continue;

            for (auto it : can[0][k1])
                for (auto it2 : can[1][k2]) {
                    if (it2.fi < it.fi + 2 || it2.se < it.se + 2)
                        continue;

                    int x = it.fi, y = it.se, xx = it2.fi, yy = it2.se;
                    aux.clear();
                    aux.push_back(dp[0][x][y]);
                    aux.push_back(dp[0][x][yy - 1] - dp[0][x][y]);
                    aux.push_back(dp[0][x][n] - dp[0][x][yy - 1]);
                    aux.push_back(dp[0][xx - 1][y] - dp[0][x][y]);
                    aux.push_back(dp[0][xx - 1][yy - 1] - dp[0][xx - 1][y] - dp[0][x][yy - 1] + dp[0][x][y]);
                    aux.push_back(dp[0][xx - 1][n] - dp[0][xx - 1][yy - 1] - dp[0][x][n] + dp[0][x][yy - 1]);
                    aux.push_back(dp[1][xx][yy]);
                    aux.push_back(dp[1][xx][y + 1] - dp[1][xx][yy]);
                    aux.push_back(dp[1][xx][1] - dp[1][xx][y + 1]);
                    
                    sort(aux.begin(), aux.end());
 
                    if (aux == fx) 
                        sol.push_back(make_pair(make_pair(x, xx - 1), make_pair(y, yy - 1)));
                }        
        }

    sort(sol.begin(), sol.end());
    cout << sol[0].fi.fi << ' ' << sol[0].fi.se << ' ' << sol[0].se.fi << ' ' << sol[0].se.se;
    return 0;
}