QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#163017#5078. Castle DesignZCKevinWA 2ms4016kbC++143.5kb2023-09-03 18:52:542023-09-03 18:52:54

Judging History

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

  • [2023-09-03 18:52:54]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4016kb
  • [2023-09-03 18:52:54]
  • 提交

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';
}

Details

Tip: Click on the bar to expand more detailed information

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'