Pagini recente » Cod sursa (job #3259015) | Cod sursa (job #2179289) | Cod sursa (job #401374) | Cod sursa (job #2353815) | Cod sursa (job #2480335)
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
#define nmax 520
using namespace std;
class instream {
public:
instream() {}
instream(const char *file_name) {
input_file=fopen(file_name,"r");
cursor=0;
fread(buffer,SIZE,1,input_file);
}
template <class T>
inline instream &operator >>(T &n) {
while((buffer[cursor]<'0'||buffer[cursor]>'9')&&buffer[cursor]!='-') {
advance();
}
int semn=1;
if (buffer[cursor]=='-')
semn=-1,advance();
n=0;
while('0'<=buffer[cursor]&&buffer[cursor]<='9') {
n=n*10+buffer[cursor]-'0';
advance();
}
n*=semn;
return *this;
}
private:
FILE *input_file;
static const int SIZE=1<<16;
int cursor;
char buffer[SIZE];
inline void advance() {
++ cursor;
if(cursor==SIZE) {
cursor=0;
fread(buffer,SIZE,1,input_file);
}
}
};
instream f("zone.in");
ofstream g("zone.out");
vector <int> l_var, c_var;
long long a[10], b[10], c[10];
int v[nmax][nmax], l1s = nmax, l2s, c1s, c2s, n;
long long s[nmax][nmax];
int findin(long long k, int a1, int a2, long long p[])
{
for (int i = a1; i <= a2; i++)
if (p[i] == k)
return true;
return false;
}
bool ok(int l1, int c1, int l2, int c2)
{
int i;
c[1] = s[l1][c1];
c[2] = s[l1][c2] - c[1];
c[3] = s[l1][n] - c[1] - c[2];
c[4] = s[l2][c1] - c[1];
c[5] = s[l2][c2] - c[1] - c[2] - c[4];
c[6] = s[l2][n] - c[1] - c[2] - c[3] - c[4] - c[5];
c[7] = s[n][c1] - c[1] - c[4];
c[8] = s[n][c2] - c[1] - c[2] - c[4] - c[5] - c[7];
c[9] = s[n][n] - c[1] - c[2] - c[3] - c[4] - c[5] - c[6] - c[7] - c[8];
/*
cout << l1 << ' ' << l2 << ' ' << c1 << ' ' << c2 << '\n';
if (l1 == 1 && c1 == 2) {
for (i = 1; i <= 9; i++)
cout << c[i] << ' ';
cout << '\n';
}*/
sort (c + 1 , c + 10);
for (i = 1; i <= 9; i++)
if (a[i] != c[i])
return false;
return true;
}
void verif_permutation(long long p[])
{
int l1 = 1, c1 = 1, l2 , c2;
while (c1 + 2 < n && s[1][c1 + 1] <= p[1])
c1 ++;
for (; l1 + 2 < n;) {
c_var.clear();
l_var.clear();
if (s[l1][c1] == p[1]) {
for (c2 = c1 + 1; c2 < n; c2 ++)
if (findin(s[l1][c2] - s[l1][c1], 2, 9, p))
c_var.push_back(c2);
for (l2 = l1 + 1; l2 < n; l2 ++)
if (findin(s[l2][c1] - s[l1][c1], 2, 9, p))
l_var.push_back(l2);
}
for (int i = 0; i < c_var.size(); i++)
for (int j = 0; j < l_var.size(); j++) {
c2 = c_var[i];
l2 = l_var[j];
if (ok(l1, c1, l2, c2)) {
if (l1 < l1s || (l1 == l1s && l2 < l2s) || (l1 == l1s && l2 == l2s && c1 + c2 < c1s + c2s)) {
l1s = l1;
l2s = l2;
c1s = c1;
c2s = c2;
}
}
}
l1 ++;
while (c1 > 1 && s[l1][c1] > p[1])
c1--;
}
}
int main()
{
int i, j;
f >> n;
for (i = 1; i <= 9; i++)
f >> a[i];
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
f >> v[i][j];
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + 1LL * v[i][j];
/*
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++)
cout << s[i][j] << ' ';
cout << '\n';
}*/
for (i = 1; i <= 9; i++)
b[i] = a[i];
sort(a + 1, a + 10);
for (i = 1; i <= 9; i++) {
swap(b[1], b[i]);
verif_permutation(b);
swap(b[i], b[1]);
}
g << l1s << ' ' << l2s << ' ' << c1s << ' ' << c2s << '\n';
return 0;
}