Submission #212483

#	Time	Username	Problem	Language	Result	Execution time	Memory
212483		AlexLuchianov	Building 4 (JOI20_building4)	C++14	100 / 100	1314 ms	75528 KiB

building4

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
using ll = long long;

int const nmax = 1000000;

struct Info{
  int x;
  int y;
  Info operator + (Info const &a) const {
    if(x == -nmax)
      return a;
    else if(a.x == -nmax)
      return {x, y};
    assert(!(min(a.y, y) + 1 < max(x, a.x)));
    return {min(a.x, x), max(y, a.y)};
  }
  Info operator + (int const &a) const {
    return {x + a, y + a};
  }
  bool inside(int val){
    return x <= val && val <= y;
  }
};
Info dp[1 + nmax][2];
int a[1 + nmax], b[1 + nmax];

Info extract(int pos, int val){
  if(a[pos] <= val && b[pos] <= val)
    return dp[pos][0] + dp[pos][1];
  else if(a[pos] <= val) {
    return dp[pos][0];
  } else if(b[pos] <= val) {
    return dp[pos][1];
  } else
    return {-nmax, -nmax};
}
void solve(int pos, int k, int val, char ch){
  if(0 == pos)
    return ;

  if(dp[pos - 1][0].inside(k) && a[pos - 1] <= val)
    solve(pos - 1, k - 1, a[pos - 1], 'A');
  else if(dp[pos - 1][1].inside(k) && b[pos - 1] <= val)
    solve(pos - 1, k, b[pos - 1], 'B');
  else{
    cout << "Wrong";
    assert(1 < 0);
  }

  cout << ch;
}
int main()
{
  int n;
  cin >> n;
  for(int i = 1;i <= 2 * n; i++)
    cin >> a[i];
  for(int i = 1;i <= 2 * n; i++)
    cin >> b[i];
  Info sum = ((Info){0, 0}) + ((Info){1, 1});

  //*
  for(int i = 1;i <= 2 * n; i++){
    dp[i][0] = extract(i - 1, a[i]);
    if(dp[i][0].x != -nmax)
      dp[i][0] = dp[i][0] + 1;
    dp[i][1] = extract(i - 1, b[i]);
  }

  if(dp[2 * n][0].inside(n))
    solve(2 * n, n - 1, a[2 * n], 'A');
  else if(dp[2 * n][1].inside(n))
    solve(2 * n, n, b[2 * n], 'B');
  else
    cout << -1;
  //*/
  return 0;
}
/*
BABBABAABABA

*/

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:68:8: warning: variable 'sum' set but not used [-Wunused-but-set-variable]
   Info sum = ((Info){0, 0}) + ((Info){1, 1});
        ^~~

• Subtask 1: 11 / 11
• Subtask 2: 89 / 89