QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#163137#5078. Castle DesignZCKevinRE 160ms104380kbC++144.0kb2023-09-03 21:18:162023-09-03 21:18:17

Judging History

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

  • [2023-09-03 21:18:17]
  • 评测
  • 测评结果:RE
  • 用时:160ms
  • 内存:104380kb
  • [2023-09-03 21:18:16]
  • 提交

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 + (d == 1));
      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: 100
Accepted
time: 1ms
memory: 3824kb

input:

LLRLLRLLRLRLLR

output:

16

result:

ok single line: '16'

Test #2:

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

input:

RLLRLLLRRLLRLRLL

output:

20

result:

ok single line: '20'

Test #3:

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

input:

LLRRLLLLRRLL

output:

16

result:

ok single line: '16'

Test #4:

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

input:

RLLRLLRLLRLL

output:

12

result:

ok single line: '12'

Test #5:

score: 0
Accepted
time: 2ms
memory: 4108kb

input:

LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

output:

199996

result:

ok single line: '199996'

Test #6:

score: 0
Accepted
time: 0ms
memory: 4264kb

input:

LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

output:

155164

result:

ok single line: '155164'

Test #7:

score: 0
Accepted
time: 160ms
memory: 104380kb

input:

LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

output:

189748

result:

ok single line: '189748'

Test #8:

score: -100
Runtime Error

input:

LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

output:


result: