QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#643376 | #3040. Container | cyb1010 | WA | 2ms | 8716kb | C++17 | 2.3kb | 2024-10-15 20:54:59 | 2024-10-15 20:55:00 |
Judging History
answer
/**
* @author : cyb1010
* @date : 2024-10-15 17:51:37
* @file : machine.cpp
*/
#include <bits/stdc++.h>
using namespace std;
#define fo(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define fi first
#define se second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) int(v.size())
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
void ckmx(int &x, int y) { x < y && (x = y); }
void ckmn(int &x, int y) { x > y && (x = y); }
const int N = 1010;
int __, _, n, C, c[N][2], f[N][N], fr[N][N], t[N];
string a, b;
vector<int> Ba, Bb[2];
vector<pair<int, int>> ans;
int F(int x) { return (C + 4) * (x / 2) + (x % 2) * (C + 3); }
int main() {
// fo("machine");
cin.tie(0)->sync_with_stdio(0);
cin >> _ >> n >> C >> a >> b;
for (int i = 1; i <= n; i++) {
if (a[i - 1] == 'B') Ba.push_back(i);
if (b[i - 1] == 'B') Bb[i & 1].push_back(i);
c[i][0] = SZ(Bb[0]), c[i][1] = SZ(Bb[1]);
}
memset(f, 0x3f, sizeof(f)), f[0][0] = 0;
for (int i = 0; i <= c[n][0]; i++)
for (int j = 0; j <= c[n][1]; j++) {
if (i < c[n][0]) {
int x = f[i][j] + F(abs(Ba[i + j] - Bb[0][i]))
+ max(0, c[Bb[0][i]][1] - j);
if (x < f[i + 1][j]) f[i + 1][j] = x, fr[i + 1][j] = 0;
}
if (j < c[n][1]) {
int x = f[i][j] + F(abs(Ba[i + j] - Bb[1][j]))
+ max(0, c[Bb[1][j]][0] - i);
if (x < f[i][j + 1]) f[i][j + 1] = x, fr[i][j + 1] = 1;
}
}
for (int i = c[n][0], j = c[n][1]; i || j;)
t[Ba[i + j]] = (!fr[i][j] ? Bb[0][--i] : Bb[1][--j]);
for (int i = n; i; i--)
if (t[i] > i) {
for (int j = i + 2; j <= t[i]; j += 2) ans.emplace_back(j - 2, j);
if ((t[i] - i) & 1) ans.emplace_back(t[i] - 1, t[i]);
}
for (int i = 1; i <= n; i++)
if (t[i] && t[i] < i) {
for (int j = i - 2; j >= t[i]; j -= 2) ans.emplace_back(j, j + 2);
if ((i - t[i]) & 1) ans.emplace_back(t[i], t[i] + 1);
}
cout << SZ(ans) << '\n';
for (auto [l, r] : ans) cout << l << ' ' << r << '\n';
return 0 ^ __ ^ 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 8716kb
input:
5 2 11221 21112
output:
0
result:
wrong answer invalid plan.