QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167038#5078. Castle Designideograph_advantageWA 3ms4032kbC++174.7kb2023-09-06 23:45:542023-09-06 23:45:54

Judging History

你现在查看的是最新测评结果

  • [2023-09-06 23:45:54]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:4032kb
  • [2023-09-06 23:45:54]
  • 提交

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]){
                int diff = SZ(low) - SZ(up);
                for(int j = 0; j < diff; j++) tmp.pb(up[i]);
            }
        }
        int diff = -MAX;

        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: 1ms
memory: 3436kb

input:

LLRLLRLLRLRLLR

output:

16

result:

ok single line: '16'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3404kb

input:

RLLRLLLRRLLRLRLL

output:

20

result:

ok single line: '20'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3404kb

input:

LLRRLLLLRRLL

output:

16

result:

ok single line: '16'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3476kb

input:

RLLRLLRLLRLL

output:

12

result:

ok single line: '12'

Test #5:

score: -100
Wrong Answer
time: 3ms
memory: 4032kb

input:

LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

output:

-745668512

result:

wrong answer 1st lines differ - expected: '199996', found: '-745668512'