結果
| 問題 | No.5020 Averaging |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2024-02-25 16:48:02 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,222 bytes |
| コンパイル時間 | 382 ms |
| コンパイル使用メモリ | 38,284 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 21,522,339 |
| 最終ジャッジ日時 | 2024-02-25 16:49:33 |
| 合計ジャッジ時間 | 53,349 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 33 TLE * 17 |
コンパイルメッセージ
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:283:76: warning: passing argument 5 of 'optimal_triangle_playout' from incompatible pointer type [-Wincompatible-pointer-types]
283 | 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:324:83: warning: passing argument 5 of 'greedy_optimal_triangle_playout' from incompatible pointer type [-Wincompatible-pointer-types]
324 | tmp_ans = greedy_optimal_triangle_playout(N, A, B, K - r, tmp_move[r]);
|
ソースコード
#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 0x7fffffffULstatic 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 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], min, tmp_min;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++) {tmp_min = optimal_triangle_score(N, A, B);for (i = 1, min = tmp_min; 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 (min > tmp) {min = 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];}}if (min == tmp_min) {do {i = genrand() % N + 1;j = genrand() % N + 1;} while (i == j);tmp_move[k][0] = i;tmp_move[k][1] = j;}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.95) break;for (i = 1; i <= N; i++) {A[i] = AA[i];B[i] = BB[i];}r = genrand() % 11 + 10;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;}