結果

問題 No.5020 Averaging
ユーザー 👑 ygussanyygussany
提出日時 2024-02-25 13:26:35
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 952 ms / 1,000 ms
コード長 4,007 bytes
コンパイル時間 480 ms
コンパイル使用メモリ 41,444 KB
実行使用メモリ 6,676 KB
スコア 21,810,161
最終ジャッジ日時 2024-02-25 13:27:32
合計ジャッジ時間 50,137 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 933 ms
6,676 KB
testcase_01 AC 925 ms
6,676 KB
testcase_02 AC 949 ms
6,676 KB
testcase_03 AC 952 ms
6,676 KB
testcase_04 AC 949 ms
6,676 KB
testcase_05 AC 923 ms
6,676 KB
testcase_06 AC 947 ms
6,676 KB
testcase_07 AC 947 ms
6,676 KB
testcase_08 AC 948 ms
6,676 KB
testcase_09 AC 946 ms
6,676 KB
testcase_10 AC 951 ms
6,676 KB
testcase_11 AC 948 ms
6,676 KB
testcase_12 AC 925 ms
6,676 KB
testcase_13 AC 926 ms
6,676 KB
testcase_14 AC 930 ms
6,676 KB
testcase_15 AC 924 ms
6,676 KB
testcase_16 AC 924 ms
6,676 KB
testcase_17 AC 926 ms
6,676 KB
testcase_18 AC 924 ms
6,676 KB
testcase_19 AC 924 ms
6,676 KB
testcase_20 AC 924 ms
6,676 KB
testcase_21 AC 922 ms
6,676 KB
testcase_22 AC 924 ms
6,676 KB
testcase_23 AC 923 ms
6,676 KB
testcase_24 AC 922 ms
6,676 KB
testcase_25 AC 928 ms
6,676 KB
testcase_26 AC 924 ms
6,676 KB
testcase_27 AC 921 ms
6,676 KB
testcase_28 AC 926 ms
6,676 KB
testcase_29 AC 926 ms
6,676 KB
testcase_30 AC 923 ms
6,676 KB
testcase_31 AC 923 ms
6,676 KB
testcase_32 AC 923 ms
6,676 KB
testcase_33 AC 926 ms
6,676 KB
testcase_34 AC 924 ms
6,676 KB
testcase_35 AC 923 ms
6,676 KB
testcase_36 AC 921 ms
6,676 KB
testcase_37 AC 923 ms
6,676 KB
testcase_38 AC 921 ms
6,676 KB
testcase_39 AC 950 ms
6,676 KB
testcase_40 AC 925 ms
6,676 KB
testcase_41 AC 927 ms
6,676 KB
testcase_42 AC 923 ms
6,676 KB
testcase_43 AC 923 ms
6,676 KB
testcase_44 AC 924 ms
6,676 KB
testcase_45 AC 924 ms
6,676 KB
testcase_46 AC 927 ms
6,676 KB
testcase_47 AC 948 ms
6,676 KB
testcase_48 AC 946 ms
6,676 KB
testcase_49 AC 922 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast,unroll-loops")
#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 A[], long long B[])
{
	static long long tmp;
	tmp = llabs(A[1] - THR);
	chmax(&tmp, llabs(B[1] - THR));
	if (tmp == 0) return 2000050;
	return (int)(2000000 - 100000 * log10(tmp + 1.0));
}

long long score_random_playout(int N, long long AA[], long long BB[], int K, int L)
{
	static int i, j, k;
	static long long A[46], B[46], ans, tmp;
	ans = 0;
	while (L--) {
		for (i = 1; i <= N; i++) {
			A[i] = AA[i];
			B[i] = BB[i];
		}
		for (k = 1; k <= K; 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;
		}
		ans += score(N, A, B);
	}
	return ans;
}

int random_playout_based_greedy(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, tmpp[2][2], max;
	for (i = 1; i <= N; i++) {
		A[i] = AA[i];
		B[i] = BB[i];
	}
	for (k = 1; k <= K; k++) {
		if (A[i] == THR && B[i] == THR) return -(k - 1);
		for (i = 1, max = 0; i <= N; i++) {
			for (j = i + 1; j <= N; j++) {
				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 = score_random_playout(N, A, B, K - k, 40);
				if (max < tmp) {
					max = tmp;
					move[k][0] = i;
					move[k][1] = j;
				}

				A[i] = tmpp[0][0];
				A[j] = tmpp[0][1];
				B[i] = tmpp[1][0];
				B[j] = tmpp[1][1];
			}
		}
		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;
	}
	return score(N, A, B);
}

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, move[51][2];
	k = random_playout_based_greedy(N, A, B, 50, move);
	// printf("%d\n", k);
	if (k <= 0) k *= -1;
	else k = 50;
	printf("%d\n", k);
	for (i = 1; i <= k; i++) printf("%d %d\n", move[i][0], move[i][1]);
	fflush(stdout);
	return 0;
}
0