Submission #28901

#	Time	Username	Problem	Language	Result	Execution time	Memory
28901		kriii	Test Data Creation (FXCUP2_testdata)	C++14	1 / 1	3779 ms	4844 KiB

testdata

#include <stdio.h>

int N,M,T[300*300];
bool ans[300*300];

const int non = 0x0f0f0f0f;
const int per = 700;
const int base = 300;
int S1[per][base*2+1];
int S2[per][base*2+1];

void upd(int s[per][base*2+1], int i, int k, int x)
{
	i %= per;
	if (s[i][k] > x)
		s[i][k] = x;
}

int go(int i1, int k1, int i2, int k2)
{
	if (i1 == i2 && k1 == k2) return T[i1+k1-base];
	int r1 = (i1 + i2) / 2 + 150;
	if (r1 >= i2) r1 = i2;
	int l2 = (i1 + i2) / 2 - 150;
	if (l2 <= i1) l2 = i1;

	for (int i=i1;i<=r1;i++) for (int k=0;k<=base*2;k++) S1[i%per][k] = non;
	S1[i1%per][k1] = T[i1] + (k1 != base ? T[i1+k1-base] : 0);
	for (int i=i1;i<=r1;i++){
		int px = i / M, py = i % M;
		for (int k=0;k<=base*2;k++){
			int &s = S1[i%per][k];
			if (s != non){
				if (k >= base){
					if (px + 1 < N) upd(S1,i+M,k-M,s+(k-M!=base?T[i+M]:0));
					if (py + 1 < M) upd(S1,i+1,k-1,s+(k-1!=base?T[i+1]:0));
				}
				else{
					int qx = (i + k - base) / N, qy = (i + k - base) % N;
					if (qx + 1 < M) upd(S1,i,k+N,s+(k+N!=base?T[i+k+N-base]:0));
					if (qy + 1 < N) upd(S1,i,k+1,s+(k+1!=base?T[i+k+1-base]:0));
				}
			}
			S1[(i+per/2)%per][k] = non;
		}
	}

	for (int i=l2;i<=i2;i++) for (int k=0;k<=base*2;k++) S2[i%per][k] = non;
	S2[i2%per][k2] = T[i2] + (k2 != base ? T[i2+k2-base] : 0);
	for (int i=i2;i>=l2;i--){
		int px = i / M, py = i % M;
		for (int k=base*2;k>=0;k--){
			int &s = S2[i%per][k];
			if (s != non){
				if (px > 0 && base <= k + M && k + M <= base*2) upd(S2,i-M,k+M,s+(k+M!=base?T[i-M]:0));
				if (py > 0 && base <= k + 1 && k + 1 <= base*2) upd(S2,i-1,k+1,s+(k+1!=base?T[i-1]:0));

				int qx = (i + k - base) / N, qy = (i + k - base) % N;
				if (qx > 0 && 0 <= k - N && k - N < base) upd(S2,i,k-N,s+T[i+k-N-base]);
				if (qy > 0 && 0 <= k - 1 && k - 1 < base) upd(S2,i,k-1,s+T[i+k-1-base]);
			}
			S2[(i+per/2)%per][k] = non;
		}
	}

	int mx = non, ci, ck;
	for (int i=l2;i<=r1;i++){
		for (int k=0;k<=base*2;k++){
			if (i == i1 && k == k1) continue;
			if (i == i2 && k == k2) continue;
			int now = S1[i%per][k] + S2[i%per][k];
			if (now >= non) continue;
			now -= T[i] + (k != base ? T[i+k-base] : 0);
			if (mx > now){
				mx = now;
				ci = i; ck = k;
			}
		}
	}

	if (mx == non) return 0;
	ans[ci] = ans[ci+ck-base] = 1;
	go(i1,k1,ci,ck);
	go(ci,ck,i2,k2);
	return mx;
}

int main()
{
	scanf ("%d %d",&M,&N);
	for (int i=0;i<M*N;i++) scanf ("%d",&T[i]);

	printf ("%d\n",go(0,base,N*M-1,base));
	ans[0] = ans[N*M-1] = 1;
	for (int i=0;i<M*N;i++) printf("%d%c",ans[i]?1:0,(i+1)%M==0?'\n':' ');

	return 0;
}

Compilation message (stderr)

testdata.cpp: In function 'int main()':
testdata.cpp:90:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&M,&N);
                       ^
testdata.cpp:91:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0;i<M*N;i++) scanf ("%d",&T[i]);
                                            ^
testdata.cpp: In function 'int go(int, int, int, int)':
testdata.cpp:84:17: warning: 'ck' may be used uninitialized in this function [-Wmaybe-uninitialized]
  go(ci,ck,i2,k2);
                 ^
testdata.cpp:84:17: warning: 'ci' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 1 / 1