QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #780036 | #9802. Light Up the Grid | pei | WA | 164ms | 3816kb | C++23 | 4.7kb | 2024-11-24 23:51:12 | 2024-11-29 22:50:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf INT32_MAX
#define x first
#define y second
#define endl '\n'
struct Node {
pair<int, int> a, b;
};
bool operator==(Node aa, Node bb) {
return aa.a == bb.a && aa.b == bb.b;
}
int res;
int a, b, c, d;
int cnt1, cnt2, cnt3, cnt4;
Node x, y;
void dfs(int sum) {
if (x == y) {
res = min(res, sum);
return;
}
if (cnt1 >= 4 || cnt2 >= 4 || cnt3 >= 4 || cnt4 >= 4 || sum >= res) {
return;
}
if (x.a.x != y.a.x) {
cnt1++;
x.a.x ^= 1;
dfs(sum + a);
cnt1--;
x.a.x ^= 1;
cnt2++;
x.a.x ^= 1;
x.a.y ^= 1;
dfs(sum + b);
cnt2--;
x.a.x ^= 1;
x.a.y ^= 1;
cnt3++;
x.a.x ^= 1;
x.b.x ^= 1;
dfs(sum + c);
cnt3--;
x.a.x ^= 1;
x.b.x ^= 1;
cnt4++;
x.a.x ^= 1;
x.a.y ^= 1;
x.b.x ^= 1;
x.b.y ^= 1;
dfs(sum + d);
cnt4--;
x.a.x ^= 1;
x.a.y ^= 1;
x.b.x ^= 1;
x.b.y ^= 1;
}
if (x.a.y != y.a.y) {
cnt1++;
x.a.y ^= 1;
dfs(sum + a);
cnt1--;
x.a.y ^= 1;
cnt2++;
x.a.x ^= 1;
x.a.y ^= 1;
dfs(sum + b);
cnt2--;
x.a.x ^= 1;
x.a.y ^= 1;
cnt3++;
x.a.y ^= 1;
x.b.y ^= 1;
dfs(sum + c);
cnt3--;
x.a.y ^= 1;
x.b.y ^= 1;
cnt4++;
x.a.x ^= 1;
x.a.y ^= 1;
x.b.x ^= 1;
x.b.y ^= 1;
dfs(sum + d);
cnt4--;
x.a.x ^= 1;
x.a.y ^= 1;
x.b.x ^= 1;
x.b.y ^= 1;
}
if (x.b.x != y.b.x) {
cnt1++;
x.b.x ^= 1;
dfs(sum + a);
cnt1--;
x.b.x ^= 1;
cnt2++;
x.b.x ^= 1;
x.b.y ^= 1;
dfs(sum + b);
cnt2--;
x.b.x ^= 1;
x.b.y ^= 1;
cnt3++;
x.a.x ^= 1;
x.b.x ^= 1;
dfs(sum + c);
cnt3--;
x.a.x ^= 1;
x.b.x ^= 1;
cnt4++;
x.a.x ^= 1;
x.a.y ^= 1;
x.b.x ^= 1;
x.b.y ^= 1;
dfs(sum + d);
cnt4--;
x.a.x ^= 1;
x.a.y ^= 1;
x.b.x ^= 1;
x.b.y ^= 1;
}
if (x.b.y != y.b.y) {
cnt1++;
x.b.y ^= 1;
dfs(sum + a);
cnt1--;
x.b.y ^= 1;
cnt2++;
x.b.x ^= 1;
x.b.y ^= 1;
dfs(sum + b);
cnt2--;
x.b.x ^= 1;
x.b.y ^= 1;
cnt3++;
x.a.y ^= 1;
x.b.y ^= 1;
dfs(sum + c);
cnt3--;
x.a.y ^= 1;
x.b.y ^= 1;
cnt4++;
x.a.x ^= 1;
x.a.y ^= 1;
x.b.x ^= 1;
x.b.y ^= 1;
dfs(sum + d);
cnt4--;
x.a.x ^= 1;
x.a.y ^= 1;
x.b.x ^= 1;
x.b.y ^= 1;
}
}
void solve() {
int t;
cin >> t;
cin >> a >> b >> c >> d;
while (t--) {
int n;
cin >> n;
vector<Node> arr(n + 1);
for (int i = 1; i <= n; i++) {
char aa, bb, cc, dd;
cin >> aa >> bb;
cin >> cc >> dd;
arr[i].a.x = aa - '0';
arr[i].a.y = bb - '0';
arr[i].b.x = cc - '0';
arr[i].b.y = dd - '0';
}
int temp, sum;
int ans = 0;
deque<Node> q;
Node tmp = {{1, 1},
{1, 1}};
q.push_back(tmp);
while (arr.size() > 1) {
int pos = -1;
temp = inf;
res = inf;
for (int j = 1; j < arr.size(); j++) {
cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0;
if (q.back() == arr[j])
res = min(res, 2 * min(a, min(b, min(c, d))));
else {
y = arr[j];
x = q.back();
dfs(0);
}
if (res < temp) {
temp = res;
pos = j;
}
}
ans += temp;
q.push_back(arr[pos]);
arr.erase(arr.begin() + pos);
}
cout << ans << endl;
}
}
signed main() {
#ifdef ONLINE_JUDGE
#else
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 44ms
memory: 3548kb
input:
2 1000 100 10 1 4 10 00 01 00 00 10 00 01 1 11 11
output:
1121 2
result:
ok 2 number(s): "1121 2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
2 1 1 1 1 4 10 00 01 00 00 10 00 01 1 11 11
output:
5 2
result:
ok 2 number(s): "5 2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 1000000 1000000 1000000 1000000 1 11 11
output:
2000000
result:
ok 1 number(s): "2000000"
Test #4:
score: -100
Wrong Answer
time: 164ms
memory: 3576kb
input:
10000 8 2 7 8 8 00 01 00 11 00 10 11 11 10 10 01 10 01 00 10 11 8 11 01 11 00 01 10 11 11 00 01 01 01 01 00 11 10 9 00 00 01 01 10 11 00 01 11 10 11 00 11 11 00 11 01 10 9 11 11 10 00 11 00 11 01 00 10 01 11 00 01 01 01 10 01 11 00 01 01 01 10 10 00 11 11 11 11 10 ...
output:
34 32 36 36 40 38 42 38 40 42 36 44 34 37 39 34 29 39 40 40 38 41 46 38 31 40 37 38 34 35 32 42 34 38 42 40 46 34 39 36 29 38 40 40 45 39 39 38 38 40 42 29 43 42 36 42 46 40 41 34 42 40 37 33 34 40 38 37 42 40 36 38 29 34 34 38 36 39 38 38 36 38 35 36 36 34 42 42 38 38 40 40 40 42 38 29 36 40 38 36 ...
result:
wrong answer 6th numbers differ - expected: '36', found: '38'