QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#167042 | #5078. Castle Design | ideograph_advantage | WA | 263ms | 1054160kb | C++17 | 4.7kb | 2023-09-06 23:49:45 | 2023-09-06 23:49:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb(a) emplace_back(a)
#define mp(a, b) make_pair(a, b)
#define ff first
#define ss second
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define SZ(a) int(a.size())
#ifdef LOCAL
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cerr << *l << " ", l++;
cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif
typedef long long ll;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll MOD = 1000000007;
const ll MAX = 1e9;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.ff << ',' << p.ss << ')';
}
ll ifloor(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a < 0) return (a - b + 1) / b;
else return a / b;
}
ll iceil(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a > 0) return (a + b - 1) / b;
else return a / b;
}
#define X ff
#define Y ss
int main(){
StarBurstStream;
string s;
cin >> s;
int n = SZ(s);
vector<pii> dir = {pii(1, 0), pii(0, 1), pii(-1, 0), pii(0, -1)};
int cur = 0;
vector<int> hor(n / 2), ver(n / 2);
for(int i = 0; i < n; i++){
debug("test", i, cur, dir[cur]);
if(i % 2 == 0) hor[i / 2] = dir[cur].X;
else ver[i / 2] = dir[cur].Y;
if(s[i] == 'L') cur = (cur + 1) % 4;
else cur = (cur - 1 + 4) % 4;
}
pary(iter(hor));
pary(iter(ver));
auto check = [&](vector<int> &v){
int p01 = -1, p10 = -1;
for(int i = 0; i < SZ(v); i++){
if(v[i] == -1 && v[(i + 1) % SZ(v)] == 1){
if(p01 != -1) return pii(-1, -1);
p01 = i;
}
else if(v[i] == 1 && v[(i + 1) % SZ(v)] == -1){
if(p10 != -1) return pii(-1, -1);
p10 = i;
}
}
return pii((p01 + 1) % SZ(v), (p10 + 1) % SZ(v));
};
auto [p01, p10] = check(hor);
auto rot = [&](){
debug("rot");
hor.swap(ver);
for(int i = 0; i < n / 2; i++) hor[i] = -hor[i];
rotate(ver.begin(), ver.begin() + 1, ver.end());
tie(p01, p10) = check(hor);
pary(iter(hor));
pary(iter(ver));
};
auto fix = [&](){
rotate(hor.begin(), hor.begin() + p01, hor.end());
rotate(ver.begin(), ver.begin() + p01, ver.end());
debug("fix", p01, p10);
pary(iter(hor));
pary(iter(ver));
p10 = (p10 - p01 + n / 2) % (n / 2);
p01 = 0;
};
if(p01 == -1){
debug("rotate");
rot();
}
fix();
if(p10 < n / 2 - p10){
rot();
rot();
fix();
}
debug("p", p01, p10);
vector<int> low, up;
cur = 0;
for(int i = 0; i < p10; i++){
low.pb(cur);
cur += ver[i];
}
cur = 0;
for(int i = n / 2 - 1; i >= p10; i--){
cur -= ver[i];
up.pb(cur);
}
pary(iter(low));
pary(iter(up));
if(check(ver) != pii(-1, -1)){
debug("2-mono");
vector<int> tmp;
bool ok = false;
for(int i = 0; i < SZ(up); i++){
tmp.pb(up[i]);
if(!ok && ((i + 1 < SZ(up) && up[i] > up[i + 1]) || i + 1 == SZ(up))){
int diff = SZ(low) - SZ(up);
for(int j = 0; j < diff; j++) tmp.pb(up[i]);
}
}
int diff = -MAX;
pary(iter(tmp));
for(int i = 0; i < SZ(low); i++){
diff = max(diff, low[i] - tmp[i] + 1);
if(i + 1 < SZ(low)) diff = max(diff, max(low[i], low[i + 1]) - min(tmp[i], tmp[i + 1]) + 1);
}
int ans = SZ(low) * 2 + n / 2 - 2;
ans += up[0] - low[0] + diff;
ans += up.back() - low.back() + diff;
cout << ans << "\n";
return 0;
}
vector<int> dp(SZ(up), MAX);
dp[0] = 1;
for(int i = 1; i < SZ(low); i++){
for(int j = SZ(up) - 1; j >= 0; j--){
int t1 = MAX;
if(j) t1 = max({dp[j - 1], low[i] - up[j] + 1, max(low[i], low[i - 1]) - min(up[j], up[j - 1]) + 1});
int t2 = max(dp[j], low[i] - up[j] + 1);
dp[j] = min(t1, t2);
}
}
int diff = dp[SZ(up) - 1];
int ans = SZ(low) * 2 + n / 2 - 2;
ans += up[0] - low[0] + diff;
ans += up.back() - low.back() + diff;
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3480kb
input:
LLRLLRLLRLRLLR
output:
16
result:
ok single line: '16'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
RLLRLLLRRLLRLRLL
output:
20
result:
ok single line: '20'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
LLRRLLLLRRLL
output:
16
result:
ok single line: '16'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
RLLRLLRLLRLL
output:
12
result:
ok single line: '12'
Test #5:
score: 0
Accepted
time: 2ms
memory: 4276kb
input:
LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...
output:
199996
result:
ok single line: '199996'
Test #6:
score: 0
Accepted
time: 3ms
memory: 4316kb
input:
LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...
output:
155164
result:
ok single line: '155164'
Test #7:
score: 0
Accepted
time: 3ms
memory: 4360kb
input:
LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...
output:
189748
result:
ok single line: '189748'
Test #8:
score: -100
Wrong Answer
time: 263ms
memory: 1054160kb
input:
LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...
output:
107738
result:
wrong answer 1st lines differ - expected: '137900', found: '107738'