結果

問題 No.2236 Lights Out On Simple Graph
ユーザー chro_96
提出日時 2023-03-03 22:22:28
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,724 bytes
コンパイル時間 214 ms
コンパイル使用メモリ 31,872 KB
実行使用メモリ 34,652 KB
最終ジャッジ日時 2024-09-17 23:25:43
合計ジャッジ時間 16,574 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 41 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <stdlib.h>
int cmp_ll (const void *ap, const void *bp) {
long long a = *(long long *)ap;
long long b = *(long long *)bp;
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
}
int main () {
int n = 0;
int m = 0;
long long a[40] = {};
long long b[40] = {};
long long c = 0LL;
int res = 0;
int ans = 0;
long long cbit = 0LL;
long long half[1048576][2] = {};
res = scanf("%d", &n);
res = scanf("%d", &m);
for (int i = 0; i < m; i++) {
res = scanf("%lld", a+i);
res = scanf("%lld", b+i);
a[i] -= 1LL;
b[i] -= 1LL;
}
for (int i = 0; i < n; i++) {
res = scanf("%lld", &c);
cbit |= (c<<((long long)i));
}
ans = m+1;
for (int i = 0; i < (1<<(m/2)); i++) {
for (int j = 0; j < m/2; j++) {
if ((i&(1<<j)) > 0) {
half[i][1] += 1LL;
half[i][0] ^= (1LL<<a[j]);
half[i][0] ^= (1LL<<b[j]);
}
}
}
qsort(half, (1<<(m/2)), sizeof(long long)*2, cmp_ll);
for (int i = 0; i < (1<<(m-m/2)); i++) {
long long hbit = 0LL;
int cnt = 0;
int idx[2] = { 0, (1<<m/2) };
for (int j = 0; j < m-m/2; j++) {
if ((i&(1<<j)) > 0) {
cnt++;
hbit ^= (1LL<<a[j+m/2]);
hbit ^= (1LL<<b[j+m/2]);
}
}
while (idx[1] - idx[0] > 1) {
int nxt = (idx[0]+idx[1])/2;
if (half[nxt][0] <= (cbit^hbit)) {
idx[0] = nxt;
} else {
idx[1] = nxt;
}
}
if (half[idx[0]][0] == (cbit^hbit) && ans > cnt+((int)half[idx[0]][1])) {
ans = cnt+((int)half[idx[0]][1]);
}
}
if (ans > m) {
printf("-1\n");
return 0;
}
printf("%d\n", ans);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0