Submission #3080964

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
	int x;
	int y;
}pos;

pos *va, *vb;
int **E;

int ABS(int x){
	return x >= 0 ? x : -x;
}

int max(int a, int b){
	return a >= b ? a : b;
}

int qurt(int x){
	int a;
	for(a = 1; a * a < x; a++){}
	return a;
}

void put(int x, int y, int N, int **KG, int *is_used){
	int i, s, t, sum, now_max = -1, now_num = 0;
	for(i = 1; i <= N; i++){
		if(is_used[i] == 0){
			sum = 0;
			for(s = -1; s <= 1; s++){
				for(t = -1; t <= 1; t++){
					sum += E[i][KG[x + s][y + t]];
				}
			}
			if(sum > now_max){
				now_max = sum;
				now_num = i;
			}
		}
	}
	KG[x][y] = now_num;
	is_used[now_num] = 1;
}

int swap_1x1(int x1, int y1, int x2, int y2, int **KG){
	if(x1 == x2 && y1 == y2){
		return 0;
	}
	else{
		int s, t, now_sum = 0, next_sum = 0, tmp;
		for(s = -1; s <= 1; s++){
			for(t = -1; t <= 1; t++){
				now_sum += E[KG[x1][y1]][KG[x1 + s][y1 + t]];
				now_sum += E[KG[x2][y2]][KG[x2 + s][y2 + t]];
			}
		}
		tmp = KG[x1][y1];
		KG[x1][y1] = KG[x2][y2];
		KG[x2][y2] = tmp;
		for(s = -1; s <= 1; s++){
			for(t = -1; t <= 1; t++){
				next_sum += E[KG[x1][y1]][KG[x1 + s][y1 + t]];
				next_sum += E[KG[x2][y2]][KG[x2 + s][y2 + t]];
			}
		}
		if(now_sum > next_sum){
			tmp = KG[x1][y1];
			KG[x1][y1] = KG[x2][y2];
			KG[x2][y2] = tmp;
			return 0;
		}
		else{
			return next_sum - now_sum;
		}
	}
}

int P[24][4] = {{0, 1, 2, 3},
				{0, 1, 3, 2},
				{0, 2, 1, 3},
				{0, 2, 3, 1},
				{0, 3, 1, 2},
				{0, 3, 2, 1},
				{1, 0, 2, 3},
				{1, 0, 3, 2},
				{1, 2, 0, 3},
				{1, 2, 3, 0},
				{1, 3, 0, 2},
				{1, 3, 2, 0},
				{2, 0, 1, 3},
				{2, 0, 3, 1},
				{2, 1, 0, 3},
				{2, 1, 3, 0},
				{2, 3, 0, 1},
				{2, 3, 1, 0},
				{3, 0, 1, 2},
				{3, 0, 2, 1},
				{3, 1, 0, 2},
				{3, 1, 2, 0},
				{3, 2, 0, 1},
				{3, 2, 1, 0}};

int optimization_2x2(int x, int y, int **KG){
	int A[4][4], C[4], i, j, k, s, t;
	for(i = 0; i <= 1; i++){
		for(j = 0; j <= 1; j++){
			C[2 * i + j] = KG[x + i][y + j];
			KG[x + i][y + j] = 0;
		}
	}
	for(i = 0; i < 4; i++){
		for(j = 0; j < 4; j++){
			A[i][j] = 0;
		}
	}
	for(k = 0; k < 4; k++){
		for(i = 0; i <= 1; i++){
			for(j = 0; j <= 1; j++){
				for(s = -1; s <= 1; s++){
					for(t = -1; t <= 1; t++){
						A[k][2 * i + j] += E[C[k]][KG[x + i + s][y + j + t]];
					}
				}
			}
		}
	}
	int sum, first_sum, sum_max = -1, max_num;
	for(i = 0; i < 24; i++){
		sum = 0;
		for(j = 0; j < 4; j++){
			sum += A[P[i][j]][j];
		}
		if(sum > sum_max){
			if(i == 0){
				first_sum = sum;
			}
			sum_max = sum;
			max_num = i;
		}
	}
	for(i = 0; i <= 1; i++){
		for(j = 0; j <= 1; j++){
			KG[x + i][y + j] = C[P[max_num][2 * i + j]];
		}
	}
	return sum_max - first_sum;
}

int swap_2_to_2(int e1, int e2, int **KG){
	if(max(ABS(va[e1].x - va[e2].x), ABS(va[e1].y - va[e2].y)) <= 1
	 || max(ABS(va[e1].x - vb[e2].x), ABS(va[e1].y - vb[e2].y)) <= 1
	  || max(ABS(vb[e1].x - va[e2].x), ABS(vb[e1].y - va[e2].y)) <= 1
	   || max(ABS(vb[e1].x - vb[e2].x), ABS(vb[e1].y - vb[e2].y)) <= 1){
		return 0;
	}
	else{
		int i, j, s, t, now_sum = 0, next_sum = 0, tmp, res, sub_res = 0;
		sub_res += swap_1x1(va[e1].x, va[e1].y, vb[e1].x, vb[e1].y, KG);
		sub_res += swap_1x1(va[e2].x, va[e2].y, vb[e2].x, vb[e2].y, KG);
		for(s = -1; s <= 1; s++){
			for(t = -1; t <= 1; t++){
				now_sum += E[KG[va[e1].x][va[e1].y]][KG[va[e1].x + s][va[e1].y + t]];
				now_sum += E[KG[vb[e1].x][vb[e1].y]][KG[vb[e1].x + s][vb[e1].y + t]];
				now_sum += E[KG[va[e2].x][va[e2].y]][KG[va[e2].x + s][va[e2].y + t]];
				now_sum += E[KG[vb[e2].x][vb[e2].y]][KG[vb[e2].x + s][vb[e2].y + t]];
			}
		}
		tmp = KG[va[e1].x][va[e1].y];
		KG[va[e1].x][va[e1].y] = KG[va[e2].x][va[e2].y];
		KG[va[e2].x][va[e2].y] = tmp;
		tmp = KG[vb[e1].x][vb[e1].y];
		KG[vb[e1].x][vb[e1].y] = KG[vb[e2].x][vb[e2].y];
		KG[vb[e2].x][vb[e2].y] = tmp;
		res = swap_1x1(va[e1].x, va[e1].y, vb[e1].x, vb[e1].y, KG);
		res = swap_1x1(va[e2].x, va[e2].y, vb[e2].x, vb[e2].y, KG);
		for(s = -1; s <= 1; s++){
			for(t = -1; t <= 1; t++){
				next_sum += E[KG[va[e1].x][va[e1].y]][KG[va[e1].x + s][va[e1].y + t]];
				next_sum += E[KG[vb[e1].x][vb[e1].y]][KG[vb[e1].x + s][vb[e1].y + t]];
				next_sum += E[KG[va[e2].x][va[e2].y]][KG[va[e2].x + s][va[e2].y + t]];
				next_sum += E[KG[vb[e2].x][vb[e2].y]][KG[vb[e2].x + s][vb[e2].y + t]];
			}
		}
		if(now_sum > next_sum){
			tmp = KG[va[e1].x][va[e1].y];
			KG[va[e1].x][va[e1].y] = KG[va[e2].x][va[e2].y];
			KG[va[e2].x][va[e2].y] = tmp;
			tmp = KG[vb[e1].x][vb[e1].y];
			KG[vb[e1].x][vb[e1].y] = KG[vb[e2].x][vb[e2].y];
			KG[vb[e2].x][vb[e2].y] = tmp;
			res = swap_1x1(va[e1].x, va[e1].y, vb[e1].x, vb[e1].y, KG);
			res = swap_1x1(va[e2].x, va[e2].y, vb[e2].x, vb[e2].y, KG);
			return sub_res;
		}
		else{
			return next_sum - now_sum + sub_res;
		}
	}
}

/*
int swap_1x2_1x2(int x1, int y1, int x2, int y2, int **KG){
	if(x1 == x2 && ABS(y1 - y2) <= 2){
		return 0;
	}
	else{
		int i, j, s, t, now_sum = 0, next_sum = 0, tmp, res, sub_res = 0;
		sub_res += swap_1x1(x1, y1, x1, y1 + 1, KG);
		sub_res += swap_1x1(x2, y2, x2, y2 + 1, KG);
		for(s = -1; s <= 1; s++){
			for(t = -1; t <= 1; t++){
				now_sum += E[KG[x1][y1]][KG[x1 + s][y1 + t]];
				now_sum += E[KG[x1][y1 + 1]][KG[x1 + s][y1 + 1 + t]];
				now_sum += E[KG[x2][y2]][KG[x2 + s][y2 + t]];
				now_sum += E[KG[x2][y2 + 1]][KG[x2 + s][y2 + 1 + t]];
			}
		}
		tmp = KG[x1][y1];
		KG[x1][y1] = KG[x2][y2];
		KG[x2][y2] = tmp;
		tmp = KG[x1][y1 + 1];
		KG[x1][y1 + 1] = KG[x2][y2 + 1];
		KG[x2][y2 + 1] = tmp;
		res = swap_1x1(x1, y1, x1, y1 + 1, KG);
		res = swap_1x1(x2, y2, x2, y2 + 1, KG);
		for(s = -1; s <= 1; s++){
			for(t = -1; t <= 1; t++){
				next_sum += E[KG[x1][y1]][KG[x1 + s][y1 + t]];
				next_sum += E[KG[x1][y1 + 1]][KG[x1 + s][y1 + 1 + t]];
				next_sum += E[KG[x2][y2]][KG[x2 + s][y2 + t]];
				next_sum += E[KG[x2][y2 + 1]][KG[x2 + s][y2 + 1 + t]];
			}
		}
		if(now_sum > next_sum){
			tmp = KG[x1][y1];
			KG[x1][y1] = KG[x2][y2];
			KG[x2][y2] = tmp;
			tmp = KG[x1][y1 + 1];
			KG[x1][y1 + 1] = KG[x2][y2 + 1];
			KG[x2][y2 + 1] = tmp;
			res = swap_1x1(x1, y1, x1, y1 + 1, KG);
			res = swap_1x1(x2, y2, x2, y2 + 1, KG);
			return sub_res;
		}
		else{
			return next_sum - now_sum;
		}
	}
}
*/
/*
int swap_2x2(int x1, int y1, int x2, int y2, int **KG){
	if(ABS(x1 - x2) <= 2 && ABS(y1 - y2) <= 2){
		return 0;
	}
	else{
		int i, j, s, t, now_sum = 0, next_sum = 0, tmp, res;
		res = optimization_2x2(x1, y1, KG);
		res = optimization_2x2(x2, y2, KG);
		for(i = 0; i <= 1; i++){
			for(j = 0; j <= 1; j++){
				for(s = -1; s <= 1; s++){
					for(t = -1; t <= 1; t++){
						now_sum += E[KG[x1 + i][y1 + j]][KG[x1 + i + s][y1 + j + t]];
						now_sum += E[KG[x2 + i][y2 + j]][KG[x2 + i + s][y2 + j + t]];
					}
				}
			}
		}
		for(i = 0; i <= 1; i++){
			for(j = 0; j <= 1; j++){
				tmp = KG[x1 + i][y1 + j];
				KG[x1 + i][y1 + j] = KG[x2 + i][y2 + j];
				KG[x2 + i][y2 + j] = tmp;
			}
		}
		res = optimization_2x2(x1, y1, KG);
		res = optimization_2x2(x2, y2, KG);
		for(i = 0; i <= 1; i++){
			for(j = 0; j <= 1; j++){
				for(s = -1; s <= 1; s++){
					for(t = -1; t <= 1; t++){
						next_sum += E[KG[x1 + i][y1 + j]][KG[x1 + i + s][y1 + j + t]];
						next_sum += E[KG[x2 + i][y2 + j]][KG[x2 + i + s][y2 + j + t]];
					}
				}
			}
		}
		if(now_sum > next_sum){
			for(i = 0; i <= 1; i++){
				for(j = 0; j <= 1; j++){
					tmp = KG[x1 + i][y1 + j];
					KG[x1 + i][y1 + j] = KG[x2 + i][y2 + j];
					KG[x2 + i][y2 + j] = tmp;
				}
			}
			res = optimization_2x2(x1, y1, KG);
			res = optimization_2x2(x2, y2, KG);
			return 0;
		}
		else{
			return next_sum - now_sum;
		}
	}
}
*/

int score(int K, int **KG){
	int i, j, s, t, sum = 0;
	for(i = 1; i <= K; i++){
		for(j = 1; j <= K; j++){
			for(s = -1; s <= 1; s++){
				for(t = -1; t <= 1; t++){
					sum += E[KG[i][j]][KG[i + s][j + t]];
				}
			}
		}
	}
	return sum / 2;
}

int main(){
//	FILE *file1 = fopen("testcase.in", "r"), *file2 = fopen("result.out", "w");
	int N, M, u, v, w, i, j;
	scanf("%d%d", &N, &M);
	E = (int **)malloc(sizeof(int *) * (N + 1));
	for(i = 0; i <= N; i++){
		E[i] = (int *)malloc(sizeof(int) * (N + 1));
		for(j = 0; j <= N; j++){
			E[i][j] = 0;
		}
	}
	for(i = 0; i < M; i++){
		scanf("%d%d%d", &u, &v, &w);
		E[u][v] = w;
		E[v][u] = w;
	}
	int Vemb, Eemb;
	scanf("%d%d", &Vemb, &Eemb);
	int K = qurt(N), L = qurt(Vemb);
	int z1, z2;
	va = (pos *)malloc(sizeof(pos) * Eemb);
	vb = (pos *)malloc(sizeof(pos) * Eemb);
	for(i = 0, j = 0; i < Eemb; i++){
		scanf("%d%d", &z1, &z2);
		z1 += L - 1;
		z2 += L - 1;
		va[j].x = z1 / L;
		va[j].y = z1 % L + 1;
		vb[j].x = z2 / L;
		vb[j].y = z2 % L + 1;
		if(va[j].x <= K && va[j].y <= K && vb[j].x <= K && vb[j].y <= K){
			j++;
		}
	}
	Eemb = j;
/*	for(i = 0; i < Eemb; i++){
		printf("i = %d: (%d, %d) - (%d, %d)\n", i, va[i].x, va[i].y, vb[i].x, vb[i].y);
	}
*/
	int Repeat = 1000, r;
	int **is_used = (int **)malloc(sizeof(int *) * Repeat);
	int ***KG = (int ***)malloc(sizeof(int **) * Repeat);
	srand((unsigned)time(NULL));

/*	int rest, tmp, rand_num;
	int *rand_perm = (int *)malloc(sizeof(int) * (N + 1));
	for(i = 0; i <= N; i++){
		rand_perm[i] = i;
	}
*/	
	time_t c0 = time(NULL);
	for(r = 0; r < Repeat && time(NULL) - c0 < 10; r++){
		is_used[r] = (int *)malloc(sizeof(int) * (N + 1));
		for(i = 0; i <= N; i++){
			is_used[r][i] = 0;
		}

		KG[r] = (int **)malloc(sizeof(int *) * (K + 2));
		for(i = 0; i <= K + 1; i++){
			KG[r][i] = (int *)malloc(sizeof(int) * (K + 2));
			for(j = 0; j <= K + 1; j++){
				KG[r][i][j] = 0;
			}
		}

/*		for(i = 1, rest = N; i <= K; i++){
			for(j = 1; j <= K; j++){
				if(rest > 0){
					rand_num = rand() % rest + 1;
					KG[r][i][j] = rand_perm[rand_num];
					tmp = rand_perm[rand_num];
					rand_perm[rand_num] = rand_perm[rest];
					rand_perm[rest] = tmp;
					rest--;
				}
			}
		}
*/
		int first = rand() % N + 1;
		KG[r][1][1] = first;
		is_used[r][first] = 1;

/*		if(r % 2 == 0){
			for(i = 1; i <= K; i++){
				for(j = 1; j <= K; j++){
					if(!(i == 1 && j == 1)){
						put(i, j, N, KG[r], is_used[r]);
					}
				}
			}
		}
		else{
			for(i = 2; i <= K; i++){
				for(j = 1; j < i; j++){
					put(j, i, N, KG[r], is_used[r]);
				}
				for(j = i; j >= 1; j--){
					put(i, j, N, KG[r], is_used[r]);
				}
			}
		}
*/

		for(i = 2; i <= K; i++){
			for(j = 1; j < i; j++){
				put(j, i, N, KG[r], is_used[r]);
			}
			for(j = i; j >= 1; j--){
				put(i, j, N, KG[r], is_used[r]);
			}
		}

//		printf("(r, pre_score) = (%d, %d)\n", r, score(K, KG[r]));

		int x1, y1, x2, y2, e1, e2, swap_1x1_num, swap_2x2_num, optimization_2x2_num, swap_2_to_2_num;

		for(i = 0; i < 100; i++){
			swap_1x1_num = 0;
			for(x1 = 1; x1 <= K; x1++){
				for(y1 = 1; y1 <= K; y1++){
					for(x2 = 1; x2 <= K; x2++){
						for(y2 = 1; y2 <= K; y2++){
							swap_1x1_num += swap_1x1(x1, y1, x2, y2, KG[r]);
						}
					}
				}
			}
//			printf("(i, swap_1x1_num) = (%d, %d)\n", i, swap_1x1_num);
			optimization_2x2_num = 0;
			for(x1 = 1; x1 < K; x1++){
				for(y1 = 1; y1 < K; y1++){
					optimization_2x2_num += optimization_2x2(x1, y1, KG[r]);
				}
			}
//			printf("(i, optimization_2x2_num) = (%d, %d)\n", i, optimization_2x2_num);
			if(swap_1x1_num == 0 && optimization_2x2_num == 0){
				break;
			}
		}

/*		int border = 1;
		for(i = 0; i < 100; i++){
			swap_2_to_2_num = 0;
			for(e1 = 0; e1 < Eemb; e1++){
				for(e2 = 0; e2 < Eemb; e2++){
					if(E[KG[r][va[e1].x][va[e1].y]][KG[r][vb[e1].x][vb[e1].y]] >= border && E[KG[r][va[e2].x][va[e2].y]][KG[r][vb[e2].x][vb[e2].y]] >= border){
						swap_2_to_2_num += swap_2_to_2(e1, e2, KG[r]);
					}
				}
			}
			printf("(i, swap_2_to_2_num) = (%d, %d)\n", i, swap_2_to_2_num);
			if(swap_2_to_2_num == 0){
				break;
			}
		}
*/
/*		for(i = 0; i < 5; i++){
			swap_1x1_num = 0;
			for(x1 = 1; x1 <= K; x1++){
				for(y1 = 1; y1 <= K; y1++){
					for(x2 = 1; x2 <= K; x2++){
						for(y2 = 1; y2 <= K; y2++){
							swap_1x1_num += swap_1x1(x1, y1, x2, y2, KG[r]);
						}
					}
				}
			}
//			printf("(i, swap_1x1_num) = (%d, %d)\n", i, swap_1x1_num);
		}
*/
/*		for(i = 0; i < 5; i++){
			optimization_2x2_num = 0;
			for(x1 = 1; x1 < K; x1++){
				for(y1 = 1; y1 < K; y1++){
					optimization_2x2_num += optimization_2x2(x1, y1, KG[r]);
				}
			}
			printf("(i, optimization_2x2_num) = (%d, %d)\n", i, optimization_2x2_num);
		}
*/
	}

	Repeat = r;
//	printf("Repeat = %d\n", Repeat);

	int now_score, max_score = -1, max_num;
	for(r = 0; r < Repeat; r++){
		now_score = score(K, KG[r]);
//		printf("(r, score) = (%d, %d)\n", r, now_score);
		if(now_score > max_score){
			max_score = now_score;
			max_num = r;
		}
	}

	for(i = 1; i <= K; i++){
		for(j = 1; j <= K; j++){
			if(KG[max_num][i][j] > 0){
				printf("%d %d\n", KG[max_num][i][j], (i - 1) * L + (j - 1) + 1);
			}
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.c: In function ‘main’:
./Main.c:327:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ^
./Main.c:336:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
   ^
./Main.c:341:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &Vemb, &Eemb);
  ^
./Main.c:347:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &z1, &z2);
   ^

Judge Result