結果
問題 | No.5002 stick xor |
ユーザー | letrangerjp |
提出日時 | 2018-05-26 20:29:06 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 972 ms / 1,000 ms |
コード長 | 4,825 bytes |
コンパイル時間 | 33,182 ms |
実行使用メモリ | 956 KB |
スコア | 41,651 |
最終ジャッジ日時 | 2018-05-26 20:29:40 |
ジャッジサーバーID (参考情報) |
judge9 / |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 961 ms
952 KB |
testcase_01 | AC | 970 ms
956 KB |
testcase_02 | AC | 967 ms
956 KB |
testcase_03 | AC | 969 ms
952 KB |
testcase_04 | AC | 964 ms
956 KB |
testcase_05 | AC | 962 ms
952 KB |
testcase_06 | AC | 965 ms
956 KB |
testcase_07 | AC | 961 ms
952 KB |
testcase_08 | AC | 970 ms
952 KB |
testcase_09 | AC | 971 ms
956 KB |
testcase_10 | AC | 968 ms
952 KB |
testcase_11 | AC | 963 ms
956 KB |
testcase_12 | AC | 967 ms
956 KB |
testcase_13 | AC | 966 ms
952 KB |
testcase_14 | AC | 965 ms
952 KB |
testcase_15 | AC | 967 ms
952 KB |
testcase_16 | AC | 966 ms
956 KB |
testcase_17 | AC | 968 ms
956 KB |
testcase_18 | AC | 964 ms
952 KB |
testcase_19 | AC | 972 ms
952 KB |
testcase_20 | AC | 967 ms
952 KB |
testcase_21 | AC | 963 ms
956 KB |
testcase_22 | AC | 963 ms
952 KB |
testcase_23 | AC | 967 ms
956 KB |
testcase_24 | AC | 968 ms
956 KB |
testcase_25 | AC | 966 ms
956 KB |
testcase_26 | AC | 968 ms
952 KB |
testcase_27 | AC | 961 ms
956 KB |
testcase_28 | AC | 965 ms
956 KB |
testcase_29 | AC | 969 ms
956 KB |
testcase_30 | AC | 967 ms
952 KB |
testcase_31 | AC | 967 ms
956 KB |
ソースコード
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <string.h> const int DEBUG = 0; const int TimeLimit = 960 * 1000; static unsigned long y = 2463534242; unsigned long xorshift(void) { y = y ^ (y << 13); y = y ^ (y >> 17); return y = y ^ (y << 5); } int rnd(int max) { return xorshift() % max; } typedef struct { int l; int i; } LI_t; typedef struct { int horizonalp; int size; int i; int j; } target_t; typedef struct { int a, b, c, d; } ans_t; int N, K; int L[500]; LI_t LI[500]; int srcA[60][60], srcB[60][60]; int A[60][60], B[60][60]; int FirstScore; int cmp(const void *a, const void *b) { return ((LI_t*)b)->l - ((LI_t*)a)->l; // return ((LI_t*)a)->l - ((LI_t*)b)->l; } int count_white(void) { int res = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { res += A[i][j] ^ 1; } } return res; } int calc_score(void) { return count_white() - FirstScore; } target_t get_target(int len) { int found = 0; target_t res; int max = 0; for (int i = 0; i < N; ++i) { int sum = 0; int cusum[N+1]; cusum[0] = sum; for (int j = 0; j < N; ++j) { cusum[j+1] = sum += A[i][j]; } for (int j = 0; j <= N-len; ++j) { if (cusum[j+len] - cusum[j] > max) { found = 1; max = cusum[j+len] - cusum[j]; res.horizonalp = 1; res.size = max; res.i = i; res.j = j; if (max >= len) return res; } } } for (int i = 0; i < N; ++i) { int sum = 0; int cusum[N+1]; cusum[0] = sum; for (int j = 0; j < N; ++j) { cusum[j+1] = sum += B[i][j]; } for (int j = 0; j <= N-len; ++j) { if (cusum[j+len] - cusum[j] > max) { found = 1; max = cusum[j+len] - cusum[j]; res.horizonalp = 0; res.size = max; res.i = i; res.j = j; if (max >= len) return res; } } } if (!found) { res.horizonalp = rnd(2); res.size = -1; res.i = rnd(N); res.j = rnd(N); } return res; } void swap_by_ans(ans_t t) { for (int i = t.a-1; i <= t.c-1; ++i) { for (int j = t.b-1; j <= t.d-1; ++j) { A[i][j] ^= 1; B[j][i] ^= 1; } } } int calc_sub_by_ans(ans_t t) { int res = 0; for (int i = t.a-1; i <= t.c-1; ++i) { for (int j = t.b-1; j <= t.d-1; ++j) { res += A[i][j] == 0 ? 1 : -1; } } return res; } int calc_add_by_ans(ans_t t) { int res = 0; for (int i = t.a-1; i <= t.c-1; ++i) { for (int j = t.b-1; j <= t.d-1; ++j) { res += A[i][j] == 1 ? 1 : -1; } } return res; } void shuffle_LI(void) { for (int i = K - 1; i > 0; --i) { int j = rnd(i + 1); LI_t t = LI[i]; LI[i] = LI[j]; LI[j] = t; } } int main(void) { scanf("%d %d", &N, &K); for (int i = 0; i < K; ++i) { int l; scanf("%d", &l); L[i] = l; LI[i].l = l; LI[i].i = i; } for (int i = 0; i < N; ++i) { char s[100]; scanf("%s\n", s); for (int j = 0; j < N; ++j) { srcA[i][j] = srcB[j][i] = s[j] - 48; } } memcpy(A, srcA, sizeof(int)*N*N); memcpy(B, srcB, sizeof(int)*N*N); FirstScore = count_white(); if (DEBUG) printf("FirstScore: %d\n", FirstScore); ans_t max_ans[K]; int max_score = 0; for (;clock() < TimeLimit;) { // for (int q = 0; q < 10; ++q) { ans_t ans[K]; for (int i = 0; i < K; ++i) { int a, b, c, d; target_t target = get_target(LI[i].l); if (target.j > N - LI[i].l) target.j = N - LI[i].l; if (target.horizonalp) { for (int j = target.j; j < target.j+LI[i].l; ++j) { A[target.i][j] ^= 1; B[j][target.i] ^= 1; } a = c = target.i+1; b = target.j+1; d = target.j+LI[i].l; } else { for (int j = target.j; j < target.j+LI[i].l; ++j) { B[target.i][j] ^= 1; A[j][target.i] ^= 1; } b = d = target.i+1; a = target.j+1; c = target.j+LI[i].l; } ans[LI[i].i].a = a; ans[LI[i].i].b = b; ans[LI[i].i].c = c; ans[LI[i].i].d = d; } int score = calc_score(); if (score > max_score) { max_score = score; for (int j = 0; j < K; ++j) max_ans[j] = ans[j]; } shuffle_LI(); memcpy(A, srcA, sizeof(int)*N*N); memcpy(B, srcB, sizeof(int)*N*N); } for (int i = 0; i < K; ++i) { printf("%d %d %d %d\n", max_ans[i].a, max_ans[i].b, max_ans[i].c, max_ans[i].d); } // if (DEBUG) { // for (int i = 0; i < N; ++i) { // for (int j = 0; j < N; ++j) { // putchar(A[i][j]+48); // } // puts(""); // } // } if (DEBUG) printf("Score: %d\n", max_score); // ans_t v; // v.a = v.b = 1; // v.c = v.d = 60; // printf("%d\n", calc_add_by_ans(v)); }