QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#163017 | #5078. Castle Design | ZCKevin | WA | 2ms | 4016kb | C++14 | 3.5kb | 2023-09-03 18:52:54 | 2023-09-03 18:52:54 |
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
#define short int
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;
short 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 x = 0, y = 1, d = 0;
for (auto c : s) {
adv_d(d, c);
if (d == 1) break;
tie(x, y) = nxt({x, y}, d);
if (d == 3)
up.pb(y);
}
}
{
int x = 0, y = 0, d = 2;
for (int i = s.size()-1;i >= 0;--i) {
char c = s[i];
c = 'L' + 'R' - c;
adv_d(d, c);
DE(x, y, c);
if (d == 1) break;
tie(x, y) = nxt({x, y}, d);
if (d == 3) dn.pb(y+1);
}
}
debug(AI(up));
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;
int sup = max(0, up.back()-dn.back());
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], (short)max<int>(dp[i][j], dn[j+1] - up[i+1]));
if (j+1 < dn.size() && k)
chmin(dp[i][j+1], (short)max<int>(dp[i][j], dn[j+1] - up[i]));
if (i+1 < up.size() && !k)
chmin(dp[i+1][j], (short)max<int>(dp[i][j], dn[j] - up[i+1]));
DE(i, j, dp[i][j]);
}
int g = abs(dn.back()-up.back());
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);
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());
return s.size() + abs(x) + abs(y-1);
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
string s;
cin >> s;
if (s.size() > 10000)
cout << solve_t2(s) << '\n';
else
cout << solve_t1(s) << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3696kb
input:
LLRLLRLLRLRLLR
output:
16
result:
ok single line: '16'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
RLLRLLLRRLLRLRLL
output:
20
result:
ok single line: '20'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
LLRRLLLLRRLL
output:
16
result:
ok single line: '16'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
RLLRLLRLLRLL
output:
12
result:
ok single line: '12'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3792kb
input:
LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...
output:
199996
result:
ok single line: '199996'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...
output:
155164
result:
ok single line: '155164'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...
output:
189748
result:
ok single line: '189748'
Test #8:
score: 0
Accepted
time: 2ms
memory: 4016kb
input:
LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...
output:
137900
result:
ok single line: '137900'
Test #9:
score: -100
Wrong Answer
time: 2ms
memory: 3776kb
input:
LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...
output:
100000
result:
wrong answer 1st lines differ - expected: '100002', found: '100000'