QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#163133 | #5078. Castle Design | ZCKevin | WA | 1ms | 3596kb | C++14 | 4.0kb | 2023-09-03 21:13:43 | 2023-09-03 21:13:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
void adv_d(int &d, char t) {
d += t == 'L' ? -1 : 1;
d = (d + 4) % 4;
}
// d =
pair<int,int> nxt(pair<int,int> loc, int d) {
auto [x, y] = loc;
if (d == 0) ++y;
if (d == 1) ++x;
if (d == 2) --y;
if (d == 3) --x;
return {x, y};
}
const int inf = 60000;
const int MAX_M = 10005;
int dp[MAX_M][MAX_M];
int get_sep(string s) {
int sep = -1;
for (int i = 0;i < s.size();++i) {
if (s[i] == 'R' && s[(i+1)%s.size()] == 'R') {
sep = (i+1) % s.size();
}
}
int d = 0;
if (sep == -1) {
int n = s.size();
s += "LL";
for (int i = 0;i < n;++i) {
if (s[i] == s[i+1])
return (i+1)%n;
}
} else {
while (d != 1) {
sep = (sep + 1) % s.size();
adv_d(d, s[sep]);
DE(d, sep, s[sep]);
}
//sep = (sep - 1 + s.size()) % s.size();
}
return sep;
}
int solve_t1(string s) {
int sep = get_sep(s);
DE(sep);
for (int i = 0;i < sep;++i) s.push_back(s[i]);
s.erase(begin(s), begin(s)+sep);
DE(s);
vector<int> up, dn;
int A, B;
{
int x = 0, y = 1, d = 0;
for (auto c : s) {
adv_d(d, c);
if ( (d == 0)
|| (d == 3 && c == 'R') || d == 1)
up.pb(y);
if (d == 1) break;
A = y;
tie(x, y) = nxt({x, y}, d);
}
}
{
int x = 0, y = 1, d = 2;
for (int i = s.size()-1;i >= 0;--i) {
char c = s[i];
c = 'L' + 'R' - c;
adv_d(d, c);
if ( (d == 2)
|| (d == 3 && c == 'L') || d == 1)
dn.pb(y - (d == 1));
if (d == 1) break;
B = y;
tie(x, y) = nxt({x, y}, d);
}
}
DE(up.size());
debug(AI(up));
DE(dn.size());
debug(AI(dn));
//exit(0);
int ans = abs((int)up.size() - (int)dn.size()) + s.size();
DE(s.size());
//vector<int> dp(dn.size() + 10, inf);
for (int i = 0;i < up.size();++i) for (int j = 0;j < dn.size();++j)
dp[i][j] = inf;
dp[0][0] = 0;
bool k = up.size() < dn.size();
for (int i = 0;i < up.size();++i) for (int j = 0;j < dn.size();++j) {
if (i+1 < up.size() && j+1 < dn.size())
chmin(dp[i+1][j+1], max<int>(dp[i][j], dn[j+1] - up[i+1]));
if (j+1 < dn.size() && k)
chmin(dp[i][j+1], max<int>(dp[i][j], dn[j+1] - up[i]));
if (i+1 < up.size() && !k)
chmin(dp[i+1][j], max<int>(dp[i][j], dn[j] - up[i+1]));
DE(i, j, dp[i][j]);
}
int g = abs(A - B);
int nv = max(g, dp[up.size()-1][dn.size()-1]);
DE(ans);
DE(nv, g);
return ans + nv * 2 - g;
}
int solve_t2(string s) {
int sep = get_sep(s);
for (int i = 0;i < sep;++i) s.push_back(s[i]);
s.erase(begin(s), begin(s)+sep);
DE(s);
int x = 0, y = 1, d = 0;
for (auto c : s) {
adv_d(d, c);
tie(x, y) = nxt({x, y}, d);
}
DE(x, y, s.size());
if (s == "LLLL") return 4;
bool qq = false;
{
int n = s.size();
auto ss = s + s.substr(0, 2);
for (int i = 0;i < n;++i) {
if (ss[i] == 'L' && ss[i+1] == 'L' && ss[i+2] == 'L')
qq = true;
}
}
if (qq && x == 0 && y == 1)
return s.size() + 2;
return s.size() + abs(x) + abs(y-1);
}
bool is_t2(string s) {
s += s[0];
return s.find("RR") == string::npos;
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
string s;
cin >> s;
// if (is_t2(s))
// cout << solve_t2(s) << '\n';
// else
cout << solve_t1(s) << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3596kb
input:
LLRLLRLLRLRLLR
output:
18
result:
wrong answer 1st lines differ - expected: '16', found: '18'