제출 #237954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237954		egekabas	건물 4 (JOI20_building4)	C++14	0 / 100	6 ms	640 KiB

building4

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
pii a[1000009][2];
int n;
const int inf = 1e9;
char ans[1000009];
void change(int l, int r){
  for(int i = 0; i <= l; ++i){
    if(ans[i] == 'A')
      ans[i] = 'B';
    else
      ans[i] = 'A';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  //freopen("in.txt", "r", stdin);
  //freopen("out.txt", "w", stdout);

  cin >> n;
  n *= 2;
  for(int i = 0; i < n; ++i){
    cin >> a[i][0].ff;
    a[i][0].ss = 1;
  }
  for(int i = 0; i < n; ++i){
    cin >> a[i][1].ff;
    a[i][1].ss = -1;
    if(a[i][1].ff > a[i][0].ff){
      swap(a[i][1], a[i][0]);
    }
  }
  vector<pair<vector<int>, vector<int>>> fv;
  int val[2] = {-inf, -inf};
  vector<int> cur[2];
  for(int i = 0; i < n; ++i){
    if(a[i][0].ff < val[1]){
      cout << "-1\n";
      return 0;
    }
    else if(a[i][1].ff >= val[0] && val[0] != -1e9){
      val[0] = -1e9;
      val[1] = -1e9;
      fv.pb({cur[0], cur[1]});
      cur[0].clear();
      cur[1].clear();
      --i;
    }
    else if(a[i][1].ff >= val[1] && val[0] > a[i][1].ff && val[0] > a[i][0].ff){
      cur[0] = cur[1];
      cur[1].clear();
      val[0] = -1e9;
      val[1] = -1e9;
      fv.pb({cur[0], cur[1]});
      cur[0].clear();
      --i;
    }
    else if(a[i][0].ff >= val[1] && val[0] > a[i][1].ff && val[0] > a[i][0].ff){
      a[i][1] = a[i][0];
      --i;
    }
    else{
      val[0] = a[i][0].ff;
      val[1] = a[i][1].ff;
      cur[0].pb(a[i][0].ss);
      cur[1].pb(a[i][1].ss);
    }
  }
  if(!cur[0].empty()){
    fv.pb({cur[0], cur[1]});
  }
  int curid = 0;
  int curbal = 0;
  for(auto v : fv){
    for(int i = 0; i < v.ff.size(); ++i){
      curbal += v.ff[i];
      if(v.ff[i] == 1)
        ans[curid+i] = 'A';
      else
        ans[curid+i] = 'B';
    }
    curid += v.ff.size();
  }
  curid = 0;
  for(auto v : fv){
    int curval = 0;
    pii mini = {1e9, 1e9};
    pii maxi = {-1e9, -1e9};
    for(int i = 0; i < v.ss.size(); ++i){
      curval += v.ss[i] - v.ff[i];
      if(curval == -curbal){
        change(curid, curid+i);
        curbal = 0;
        break;
      }
      mini = min(mini, {curval, i});
      maxi = max(maxi, {curval, i});
    }
    if(curbal == 0)
      break;
    else if(curbal > 0 && mini.ff < 0){
      curbal += mini.ff;
      change(curid, mini.ss+curid);
    }
    else if(curbal < 0 && maxi.ff > 0){
      curbal += maxi.ff;
      change(curid, maxi.ss+curid);
    }
    curid += v.ff.size();
  }
  if(curbal != 0){
    cout << "-1\n";
    return 0;
  }
  for(int i = 0; i < n; ++i)
    cout << ans[i];
}

컴파일 시 표준 에러 (stderr) 메시지

building4.cpp: In function 'int main()':
building4.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.ff.size(); ++i){
                    ~~^~~~~~~~~~~~~
building4.cpp:102:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.ss.size(); ++i){
                    ~~^~~~~~~~~~~~~

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