oj.uz

Submission #217160

# Submission time Handle Problem Language Result Execution time Memory
217160 2020-03-29T07:07:36 Z rama_pang Building 4 (JOI20_building4) C++14
100 / 100
 629 ms 191468 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;

int N;
int A[MAXN * 2];
int B[MAXN * 2];


namespace solution_naive {

int memo[5005][5005][2];
string ans;

void read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  
  cin >> N;
  for (int i = 1; i <= 2 * N; i++) {
    cin >> A[i];
  }
  for (int i = 1; i <= 2 * N; i++) {
    cin >> B[i];
  }
  A[0] = B[0] = 0;
  A[2 * N + 1] = B[2 * N + 1] = 2e9;
}

int dp(int cur, int a, int last) {
  if (a > N) return 0;
  if (cur == 2 * N + 1) return a == N;
  if (memo[cur][a][last] != -1) return memo[cur][a][last];
  int res = 0;
  int prv = (last == 0 ? A[cur - 1] : B[cur - 1]);

  if (prv <= A[cur]) res = max(res, dp(cur + 1, a + 1, 0));
  if (prv <= B[cur]) res = max(res, dp(cur + 1, a, 1));
  
  return memo[cur][a][last] = res;
}

void trace(int cur, int a, int last) {
  if (cur == 2 * N + 1) return;
  int res = 0;
  int prv = (last == 0 ? A[cur - 1] : B[cur - 1]);
  if (prv <= A[cur] && dp(cur + 1, a + 1, 0) == 1) {
    ans.push_back('A');
    trace(cur + 1, a + 1, 0);
  } else if (prv <= B[cur] && dp(cur + 1, a, 1) == 1) {
    ans.push_back('B');
    trace(cur + 1, a, 1);
  }
}

void solve() {
  read();
  memset(memo, -1, sizeof(memo));
  trace(1, 0, 0);
  if (ans.empty()) ans = "-1";
  cout << ans << "\n";
}

} // NAMESPACE

namespace full_solution {

void read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  
  cin >> N;
  for (int i = 0; i < 2 * N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < 2 * N; i++) {
    cin >> B[i];
  }
}

vector<pair<int, int>> adj[MAXN * 4]; // (to, value)

void init() {
  for (int i = 0; i + 1 < 2 * N; i++) {
    if (A[i] <= A[i + 1]) adj[i * 2].emplace_back(i * 2 + 2, 1);
    if (A[i] <= B[i + 1]) adj[i * 2].emplace_back(i * 2 + 3, 0);
    if (B[i] <= A[i + 1]) adj[i * 2 + 1].emplace_back(i * 2 + 2, 1);
    if (B[i] <= B[i + 1]) adj[i * 2 + 1].emplace_back(i * 2 + 3, 0);
  }
  adj[4 * N].emplace_back(0, 1);
  adj[4 * N].emplace_back(1, 0);
}

int vis[MAXN * 4];
// set<int> all[MAXN * 4]; (all possible value of all possible paths)
pair<int, int> dp[MAXN * 4]; // all[n] has consecutive elements, save this interval in a dp of (min, max)

void dfs(int n) {
  if (vis[n]) return;
  vis[n] = 1;
  int mn = -1, mx = -1;

  // all[n] has consecutive elements due to nature of naive_dp's transition (shifting elements only by 1 position, then ORing them).

  for (auto &i : adj[n]) {
    dfs(i.first);
    if (dp[i.first] == make_pair(-1, -1)) {
      continue;
    }
    if (mn == -1 || mn > dp[i.first].first + i.second) {
      mn = dp[i.first].first + i.second;
    }
    if (mx == -1 || mx < dp[i.first].second + i.second) {
      mx = dp[i.first].second + i.second;
    }
  }
  dp[n] = make_pair(mn, mx);
}

string ans;

void trace(int n, int cur = N) {
  if (dp[n] == make_pair(-1, -1) || !(dp[n].first <= cur && cur <= dp[n].second)) {
    ans = "-1";
    return;
  }
  for (auto &i : adj[n]) {
    if (dp[i.first] != make_pair(-1, -1) && dp[i.first].first <= cur - i.second && cur - i.second <= dp[i.first].second) {
      if (i.second == 1) ans.push_back('A');
      if (i.second == 0) ans.push_back('B');
      
      trace(i.first, cur - i.second);
      return;
    }
  }
}

void solve() {
  read();
  init();

  dp[4 * N - 2] = make_pair(0, 0);
  dp[4 * N - 1] = make_pair(0, 0);
  vis[4 * N - 2] = 1;
  vis[4 * N - 1] = 1;

  dfs(4 * N);
  trace(4 * N);
  cout << ans << "\n";

}

} /// NAMESPACE

int main() {
  full_solution::solve();
  return 0;
}

Compilation message

building4.cpp: In function 'void solution_naive::trace(int, int, int)':
building4.cpp:46:7: warning: unused variable 'res' [-Wunused-variable]
   int res = 0;
       ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47488 KB Output is correct
2 Correct 32 ms 47360 KB Output is correct
3 Correct 32 ms 47360 KB Output is correct
4 Correct 32 ms 47360 KB Output is correct
5 Correct 33 ms 47608 KB Output is correct
6 Correct 33 ms 47872 KB Output is correct
7 Correct 33 ms 47872 KB Output is correct
8 Correct 34 ms 47864 KB Output is correct
9 Correct 34 ms 47864 KB Output is correct
10 Correct 34 ms 47872 KB Output is correct
11 Correct 33 ms 47864 KB Output is correct
12 Correct 34 ms 47992 KB Output is correct
13 Correct 34 ms 48000 KB Output is correct
14 Correct 34 ms 48000 KB Output is correct
15 Correct 34 ms 47992 KB Output is correct
16 Correct 34 ms 48000 KB Output is correct
17 Correct 34 ms 47992 KB Output is correct
18 Correct 34 ms 47992 KB Output is correct
19 Correct 35 ms 47992 KB Output is correct
20 Correct 34 ms 47864 KB Output is correct
21 Correct 33 ms 47864 KB Output is correct
22 Correct 39 ms 48000 KB Output is correct
23 Correct 33 ms 48000 KB Output is correct
24 Correct 33 ms 47992 KB Output is correct
25 Correct 33 ms 48000 KB Output is correct
26 Correct 33 ms 47992 KB Output is correct
27 Correct 33 ms 47872 KB Output is correct
28 Correct 33 ms 47872 KB Output is correct
29 Correct 35 ms 48000 KB Output is correct
30 Correct 33 ms 47872 KB Output is correct
31 Correct 33 ms 48000 KB Output is correct
32 Correct 33 ms 47864 KB Output is correct
33 Correct 34 ms 48000 KB Output is correct

Subtask #2
89.0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47488 KB Output is correct
2 Correct 32 ms 47360 KB Output is correct
3 Correct 32 ms 47360 KB Output is correct
4 Correct 32 ms 47360 KB Output is correct
5 Correct 33 ms 47608 KB Output is correct
6 Correct 33 ms 47872 KB Output is correct
7 Correct 33 ms 47872 KB Output is correct
8 Correct 34 ms 47864 KB Output is correct
9 Correct 34 ms 47864 KB Output is correct
10 Correct 34 ms 47872 KB Output is correct
11 Correct 33 ms 47864 KB Output is correct
12 Correct 34 ms 47992 KB Output is correct
13 Correct 34 ms 48000 KB Output is correct
14 Correct 34 ms 48000 KB Output is correct
15 Correct 34 ms 47992 KB Output is correct
16 Correct 34 ms 48000 KB Output is correct
17 Correct 34 ms 47992 KB Output is correct
18 Correct 34 ms 47992 KB Output is correct
19 Correct 35 ms 47992 KB Output is correct
20 Correct 34 ms 47864 KB Output is correct
21 Correct 33 ms 47864 KB Output is correct
22 Correct 39 ms 48000 KB Output is correct
23 Correct 33 ms 48000 KB Output is correct
24 Correct 33 ms 47992 KB Output is correct
25 Correct 33 ms 48000 KB Output is correct
26 Correct 33 ms 47992 KB Output is correct
27 Correct 33 ms 47872 KB Output is correct
28 Correct 33 ms 47872 KB Output is correct
29 Correct 35 ms 48000 KB Output is correct
30 Correct 33 ms 47872 KB Output is correct
31 Correct 33 ms 48000 KB Output is correct
32 Correct 33 ms 47864 KB Output is correct
33 Correct 34 ms 48000 KB Output is correct
34 Correct 415 ms 96888 KB Output is correct
35 Correct 479 ms 171056 KB Output is correct
36 Correct 479 ms 169136 KB Output is correct
37 Correct 494 ms 171824 KB Output is correct
38 Correct 521 ms 181296 KB Output is correct
39 Correct 488 ms 180400 KB Output is correct
40 Correct 542 ms 190572 KB Output is correct
41 Correct 552 ms 184412 KB Output is correct
42 Correct 470 ms 156596 KB Output is correct
43 Correct 526 ms 180972 KB Output is correct
44 Correct 629 ms 180972 KB Output is correct
45 Correct 515 ms 180848 KB Output is correct
46 Correct 555 ms 191468 KB Output is correct
47 Correct 521 ms 187628 KB Output is correct
48 Correct 516 ms 190444 KB Output is correct
49 Correct 535 ms 191340 KB Output is correct
50 Correct 514 ms 180588 KB Output is correct
51 Correct 510 ms 180588 KB Output is correct
52 Correct 402 ms 180844 KB Output is correct
53 Correct 393 ms 180844 KB Output is correct
54 Correct 416 ms 191260 KB Output is correct
55 Correct 398 ms 187500 KB Output is correct
56 Correct 531 ms 191468 KB Output is correct
57 Correct 476 ms 190700 KB Output is correct
58 Correct 482 ms 191340 KB Output is correct
59 Correct 460 ms 191380 KB Output is correct
60 Correct 433 ms 182704 KB Output is correct
61 Correct 477 ms 191340 KB Output is correct
62 Correct 475 ms 189292 KB Output is correct
63 Correct 461 ms 191216 KB Output is correct
64 Correct 449 ms 186288 KB Output is correct
65 Correct 471 ms 191208 KB Output is correct