#955574 (C) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	👑 ygussany
提出日時	2024-02-25 16:07:15
言語	C (gcc 12.3.0)
結果	AC
実行時間	980 ms / 1,000 ms
コード長	8,018 bytes
コンパイル時間	493 ms
コンパイル使用メモリ	38,224 KB
実行使用メモリ	6,676 KB
スコア	33,999,008
最終ジャッジ日時	2024-02-25 16:08:07
合計ジャッジ時間	51,775 ms
ジャッジサーバーID （参考情報）	judge14 / judge13
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	976 ms 6,676 KB
testcase_01	AC	951 ms 6,676 KB
testcase_02	AC	977 ms 6,676 KB
testcase_03	AC	977 ms 6,676 KB
testcase_04	AC	973 ms 6,676 KB
testcase_05	AC	972 ms 6,676 KB
testcase_06	AC	952 ms 6,676 KB
testcase_07	AC	971 ms 6,676 KB
testcase_08	AC	974 ms 6,676 KB
testcase_09	AC	973 ms 6,676 KB
testcase_10	AC	973 ms 6,676 KB
testcase_11	AC	951 ms 6,676 KB
testcase_12	AC	934 ms 6,676 KB
testcase_13	AC	972 ms 6,676 KB
testcase_14	AC	973 ms 6,676 KB
testcase_15	AC	973 ms 6,676 KB
testcase_16	AC	949 ms 6,676 KB
testcase_17	AC	976 ms 6,676 KB
testcase_18	AC	974 ms 6,676 KB
testcase_19	AC	976 ms 6,676 KB
testcase_20	AC	956 ms 6,676 KB
testcase_21	AC	972 ms 6,676 KB
testcase_22	AC	913 ms 6,676 KB
testcase_23	AC	972 ms 6,676 KB
testcase_24	AC	974 ms 6,676 KB
testcase_25	AC	949 ms 6,676 KB
testcase_26	AC	974 ms 6,676 KB
testcase_27	AC	934 ms 6,676 KB
testcase_28	AC	977 ms 6,676 KB
testcase_29	AC	974 ms 6,676 KB
testcase_30	AC	953 ms 6,676 KB
testcase_31	AC	980 ms 6,676 KB
testcase_32	AC	971 ms 6,676 KB
testcase_33	AC	973 ms 6,676 KB
testcase_34	AC	912 ms 6,676 KB
testcase_35	AC	955 ms 6,676 KB
testcase_36	AC	975 ms 6,676 KB
testcase_37	AC	974 ms 6,676 KB
testcase_38	AC	974 ms 6,676 KB
testcase_39	AC	973 ms 6,676 KB
testcase_40	AC	948 ms 6,676 KB
testcase_41	AC	976 ms 6,676 KB
testcase_42	AC	975 ms 6,676 KB
testcase_43	AC	975 ms 6,676 KB
testcase_44	AC	975 ms 6,676 KB
testcase_45	AC	952 ms 6,676 KB
testcase_46	AC	916 ms 6,676 KB
testcase_47	AC	974 ms 6,676 KB
testcase_48	AC	974 ms 6,676 KB
testcase_49	AC	976 ms 6,676 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.c: In function 'random_optimal_triangle_playout':
main.c:217:76: warning: passing argument 5 of 'optimal_triangle_playout' from incompatible pointer type [-Wincompatible-pointer-types]
  217 |                 tmp_ans = optimal_triangle_playout(N, A, B, K - r, tmp_move[r]);
      |                                                                    ~~~~~~~~^~~
      |                                                                            |
      |                                                                            int *
main.c:120:80: note: expected 'int (*)[2]' but argument is of type 'int *'
  120 | int optimal_triangle_playout(int N, long long AA[], long long BB[], int K, int move[][2])
      |                                                                            ~~~~^~~~~~~~~
main.c: In function 'greedy_optimal_triangle_playout':
main.c:274:76: warning: passing argument 5 of 'optimal_triangle_playout' from incompatible pointer type [-Wincompatible-pointer-types]
  274 |                 tmp_ans = optimal_triangle_playout(N, A, B, K - k, tmp_move[k]);
      |                                                                    ~~~~~~~~^~~
      |                                                                            |
      |                                                                            int *
main.c:120:80: note: expected 'int (*)[2]' but argument is of type 'int *'
  120 | int optimal_triangle_playout(int N, long long AA[], long long BB[], int K, int move[][2])
      |                                                                            ~~~~^~~~~~~~~
main.c: In function 'random_greedy_optimal_triangle_playout':
main.c:315:83: warning: passing argument 5 of 'greedy_optimal_triangle_playout' from incompatible pointer type [-Wincompatible-pointer-types]
  315 |                 tmp_ans = greedy_optimal_triangle_playout(N, A, B, K - r, tmp_move[r]);
      |

ソースコード

raw source code

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>

struct timeval tt;
double beg, cur;

#define MT_N 624
#define MT_M 397
#define MT_MATRIX_A 0x9908b0dfUL
#define MT_UPPER_MASK 0x80000000UL
#define MT_LOWER_MASK 0x7fffffffUL

static unsigned int mt[MT_N];
static int mti = MT_N + 1;

void init_genrand(unsigned int s)
{
    mt[0] = s & 0xffffffffUL;
    for (mti = 1; mti < MT_N; mti++) {
        mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); 
        mt[mti] &= 0xffffffffUL;
    }
}

unsigned int genrand()
{
    unsigned int y;
    static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A};

    if (mti >= MT_N) {
        int kk;
        if (mti == MT_N + 1) init_genrand(5489UL);
		
        for (kk = 0; kk < MT_N - MT_M; kk++) {
            y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
            mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL];
        }
        for (; kk < MT_N - 1; kk++) {
            y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
            mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL];
        }
        y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK);
        mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL];

        mti = 0;
    }
  
    y = mt[mti++];

    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680UL;
    y ^= (y << 15) & 0xefc60000UL;
    y ^= (y >> 18);

    return y;
}

void shuffle_permutation(int N, int p[], int K)
{
	int i, j;
	while (K--) {
		i = genrand() % N + 1;
		j = genrand() % N + 1;
		if (i != j) {
			p[i] ^= p[j];
			p[j] ^= p[i];
			p[i] ^= p[j];
		}
	}
}

void chmax(long long *a, long long b)
{
	if (*a < b) *a = b;
}

const long long THR = 500000000000000000LL;

int score(int N, long long AA[], long long BB[], int K, int move[][2])
{
	static int i, j, k;
	static long long A[46], B[46], tmp;
	for (i = 1; i <= N; i++) {
		A[i] = AA[i];
		B[i] = BB[i];
	}
	for (k = 1; k <= K; k++) {
		i = move[k][0];
		j = move[k][1];
		tmp = (A[i] + A[j]) / 2;
		A[i] = tmp;
		A[j] = tmp;
		tmp = (B[i] + B[j]) / 2;
		B[i] = tmp;
		B[j] = tmp;
	}
	// printf("%lld %lld\n", A[1], B[1]);
	tmp = llabs(A[1] - THR);
	chmax(&tmp, llabs(B[1] - THR));
	return (int)(2000000 - 100000 * log10(tmp + 1.0));
}

long long optimal_triangle_score(int N, long long AA[], long long BB[])
{
	static int ii, jj;
	static long long tmp, min;
	min = THR * 3 + 10;
	for (ii = 2; ii <= N; ii++) {
		for (jj = ii + 1; jj <= N; jj++) {
			tmp = llabs(AA[1] + AA[ii] + AA[jj] - THR * 3 - 10);
			chmax(&tmp, llabs(BB[1] + BB[ii] + BB[jj] - THR * 3 - 10));
			if (min > tmp) min = tmp;
		}
	}
	return THR * 3 + 10 - min;
}

int optimal_triangle_playout(int N, long long AA[], long long BB[], int K, int move[][2])
{
	static int i, j, k, ii, jj, argmin[2];
	static long long A[4], B[4], tmp, min;
	min = THR * 3 + 10;
	for (ii = 2; ii <= N; ii++) {
		for (jj = ii + 1; jj <= N; jj++) {
			tmp = llabs(AA[1] + AA[ii] + AA[jj] - THR * 3 - 10);
			chmax(&tmp, llabs(BB[1] + BB[ii] + BB[jj] - THR * 3 - 10));
			if (min > tmp) {
				min = tmp;
				argmin[0] = ii;
				argmin[1] = jj;
			}
		}
	}
	
	ii = argmin[0];
	jj = argmin[1];
	A[1] = AA[1];
	B[1] = BB[1];
	A[2] = AA[ii];
	B[2] = BB[ii];
	A[3] = AA[jj];
	B[3] = BB[jj];
	for (k = 1, i = 1, j = 2; k <= K; k++, j ^= 1) {
		tmp = (A[i] + A[j]) / 2;
		A[i] = tmp;
		A[j] = tmp;
		tmp = (B[i] + B[j]) / 2;
		B[i] = tmp;
		B[j] = tmp;
		move[k][0] = 1;
		move[k][1] = (j == 2)? ii: jj;
	}
	tmp = llabs(A[1] - THR);
	chmax(&tmp, llabs(B[1] - THR));
	min = tmp;
	
	if (K > 1) {
		A[1] = AA[1];
		B[1] = BB[1];
		A[2] = (AA[ii] + AA[jj]) / 2;
		B[2] = (BB[ii] + BB[jj]) / 2;
		A[3] = A[2];
		B[3] = B[2];
		for (k = 2, i = 1, j = 2; k <= K; k++, j ^= 1) {
			tmp = (A[i] + A[j]) / 2;
			A[i] = tmp;
			A[j] = tmp;
			tmp = (B[i] + B[j]) / 2;
			B[i] = tmp;
			B[j] = tmp;
		}
		tmp = llabs(A[1] - THR);
		chmax(&tmp, llabs(B[1] - THR));
		if (min > tmp) {
			move[1][0] = ii;
			move[1][1] = jj;
			for (k = 2, j = 2; k <= K; k++, j ^= 1) {
				move[k][0] = 1;
				move[k][1] = (j == 2)? ii: jj;
			}
		}
	}
	return (int)(2000000 - 100000 * log10(min + 1.0));
}

int random_optimal_triangle_playout(int N, long long AA[], long long BB[], int K, int move[][2])
{
	static int i, j, k, r, ans, tmp_ans, tmp_move[51][2];
	static long long A[46], B[46], tmp;
	ans = optimal_triangle_playout(N, AA, BB, K, move);
	while (1) {
		gettimeofday(&tt, NULL);
		cur = tt.tv_sec + (double)tt.tv_usec / 1000000;
		if (cur - beg > 0.99) break;
		
		for (i = 1; i <= N; i++) {
			A[i] = AA[i];
			B[i] = BB[i];
		}
		r = genrand() % 21 + 5;
		for (k = 1; k <= r; k++) {
			do {
				i = genrand() % N + 1;
				j = genrand() % N + 1;
			} while (i == j);
			tmp = (A[i] + A[j]) / 2;
			A[i] = tmp;
			A[j] = tmp;
			tmp = (B[i] + B[j]) / 2;
			B[i] = tmp;
			B[j] = tmp;
			tmp_move[k][0] = i;
			tmp_move[k][1] = j;
		}
		tmp_ans = optimal_triangle_playout(N, A, B, K - r, tmp_move[r]);
		if (ans < tmp_ans) {
			ans = tmp_ans;
			for (k = 1; k <= K; k++) {
				move[k][0] = tmp_move[k][0];
				move[k][1] = tmp_move[k][1];
			}
		}
	}
	return ans;
}

int greedy_optimal_triangle_playout(int N, long long AA[], long long BB[], int K, int move[][2])
{
	static int i, j, k, ii, jj, ans, tmp_ans, tmp_move[51][2];
	static long long A[46], B[46], tmp, tmpp[2][2], max;
	ans = optimal_triangle_playout(N, AA, BB, K, move);
	for (i = 1; i <= N; i++) {
		A[i] = AA[i];
		B[i] = BB[i];
	}
	for (k = 1, ii = 0, jj = 0; k <= K; k++) {
		for (i = 1, max = 0; i <= N; i++) {
			for (j = i + 1; j <= N; j++) {
				if (i == ii && j == jj) continue;
				tmpp[0][0] = A[i];
				tmpp[0][1] = A[j];
				tmpp[1][0] = B[i];
				tmpp[1][1] = B[j];
				
				tmp = (A[i] + A[j]) / 2;
				A[i] = tmp;
				A[j] = tmp;
				tmp = (B[i] + B[j]) / 2;
				B[i] = tmp;
				B[j] = tmp;
				tmp = optimal_triangle_score(N, A, B);
				if (max < tmp) {
					max = tmp;
					tmp_move[k][0] = i;
					tmp_move[k][1] = j;
				}

				A[i] = tmpp[0][0];
				A[j] = tmpp[0][1];
				B[i] = tmpp[1][0];
				B[j] = tmpp[1][1];
			}
		}
		ii = tmp_move[k][0];
		jj = tmp_move[k][1];
		tmp = (A[ii] + A[jj]) / 2;
		A[ii] = tmp;
		A[jj] = tmp;
		tmp = (B[ii] + B[jj]) / 2;
		B[ii] = tmp;
		B[jj] = tmp;
		tmp_ans = optimal_triangle_playout(N, A, B, K - k, tmp_move[k]);
		if (ans < tmp_ans) {
			ans = tmp_ans;
			for (i = 1; i <= K; i++) {
				move[i][0] = tmp_move[i][0];
				move[i][1] = tmp_move[i][1];
			}
		}
	}
	return ans;
}

int random_greedy_optimal_triangle_playout(int N, long long AA[], long long BB[], int K, int move[][2])
{
	static int i, j, k, r, ans, tmp_ans, tmp_move[51][2];
	static long long A[46], B[46], tmp;
	ans = greedy_optimal_triangle_playout(N, AA, BB, K, move);
	while (1) {
		gettimeofday(&tt, NULL);
		cur = tt.tv_sec + (double)tt.tv_usec / 1000000;
		if (cur - beg > 0.9) break;
		
		for (i = 1; i <= N; i++) {
			A[i] = AA[i];
			B[i] = BB[i];
		}
		r = genrand() % 11 + 5;
		for (k = 1; k <= r; k++) {
			do {
				i = genrand() % N + 1;
				j = genrand() % N + 1;
			} while (i == j);
			tmp = (A[i] + A[j]) / 2;
			A[i] = tmp;
			A[j] = tmp;
			tmp = (B[i] + B[j]) / 2;
			B[i] = tmp;
			B[j] = tmp;
			tmp_move[k][0] = i;
			tmp_move[k][1] = j;
		}
		tmp_ans = greedy_optimal_triangle_playout(N, A, B, K - r, tmp_move[r]);
		if (ans < tmp_ans) {
			ans = tmp_ans;
			for (k = 1; k <= K; k++) {
				move[k][0] = tmp_move[k][0];
				move[k][1] = tmp_move[k][1];
			}
		}
	}
	return ans;
}



int main()
{
	gettimeofday(&tt, NULL);
	beg = tt.tv_sec + (double)tt.tv_usec / 1000000;
	
	int i, N;
	long long A[46], B[46];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%lld %lld", &(A[i]), &(B[i]));
	
	int k = 50, ans, move[51][2];
	// ans = random_optimal_triangle_playout(N, A, B, k, move);
	// ans = greedy_optimal_triangle_playout(N, A, B, k, move);
	ans = random_greedy_optimal_triangle_playout(N, A, B, k, move);
	// printf("%d\n", score(N, A, B, k, move));
	printf("%d\n", k);
	for (i = 1; i <= k; i++) printf("%d %d\n", move[i][0], move[i][1]);
	fflush(stdout);
	return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード