oj.uz

Submission #941827

# Submission time Handle Problem Language Result Execution time Memory
941827 2024-03-09T14:10:09 Z rolandpetrean Building 4 (JOI20_building4) C++17
100 / 100
 263 ms 99376 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll

#define endl '\n'
#define pb push_back
using pi = array<int, 2>;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

/*
iau mereu cel mai mic posibil si dau switch

daca v[i][min] <= v[i + 1][min] si v[i][max] >= v[i + 1][min] si v[i][max] <= v[i + 1][max] atunci daca schimb i, schimb si i+1

pot sa iau sufix la cel mai mare interval
sufixul e un interval de valori (se schimba cu 1 costul)
v[i][0] = minimu
v[i][1] = maximu

balance = A - B
*/

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n;
  cin >> n;
  n *= 2;
  
  vector<bool> swappedv(n + 1), is_max(n + 1);
  vector<int> cost(n + 1);
  vector<vector<int>> v(n + 1, vector<int>(2));
  for (int i = 1; i <= n; ++i) cin >> v[i][0];
  for (int i = 1; i <= n; ++i) cin >> v[i][1];
  
  bool ok = true;
  int balance = 0, lastc = 0;
  for (int i = 1; i <= n; ++i) {
    if (v[i][0] <= v[i][1]) {
      if (v[i][0] >= lastc) {
        balance += 1;
        cost[i] = -1;
        
        lastc = v[i][0];
      } else {
        ok &= (v[i][1] >= lastc);
        balance -= 1;
        cost[i] = 0;
        is_max[i] = true;
        
        lastc = v[i][1];
      }
    } else {
      swappedv[i] = true;
      swap(v[i][0], v[i][1]);
      if (v[i][0] >= lastc) {
        balance -= 1;
        cost[i] = 1;
        
        lastc = v[i][0];
      } else {
        ok &= (v[i][1] >= lastc);
        balance += 1;
        cost[i] = 0;
        is_max[i] = true;
        
        lastc = v[i][1];
      }
    }
  }
  
  if (!ok) {
    cout << "-1";
    return 0;
  }
  balance /= 2;
  
  vector<pi> segments;
  int st = 1;
  for (int dr = 1; dr < n; ++dr) {
    if (cost[dr] == 0) { // sunt deja max
      segments.pb({st, dr});
      st = dr + 1;
      continue;
    }
    
    if (v[dr][1] > v[dr + 1][1]) { // nu pot da swap la asta, segmentul e invalidat
      st = dr + 1;
      continue;
    }
    
    if (v[dr][1] > v[dr + 1][0]) continue; // trebuie sa dau swap si la urmatorul
    
    // segmentul se termina aici
    segments.pb({st, dr});
    st = dr + 1;
  }
  segments.pb({st, n});
  
  /*cout << endl << endl;
  for (int i = 1; i <= n; ++i) cout << is_max[i] << " ";*/
  /*cout << endl << endl << balance << endl;
  for (pi s : segments) {
    cout << s[0] << " " << s[1] << " | ";
    for (int i = s[0]; i <= s[1]; ++i) cout << cost[i] << " ";
    cout << endl;
  }
  cout << endl;*/
  
  for (pi s : segments) {
    int l = s[0], r = s[1];
    
    int suf = 0;
    if (balance < 0) {
      int maxi = 0, maxidx = r + 1;
      for (int i = r; i >= l; --i) {
        suf += cost[i];
        if (balance + suf <= 0 && suf > maxi) {
          maxi = suf;
          maxidx = i;
        }
      }
      for (int i = r; i >= maxidx; --i) is_max[i] = true;
      
      balance += maxi;
    } else if (balance > 0) {
      int mini = 0, minidx = r + 1;
      for (int i = r; i >= l; --i) {
        suf += cost[i];
        if (balance + suf >= 0 && suf < mini) {
          mini = suf;
          minidx = i;
        }
      }
      for (int i = r; i >= minidx; --i) is_max[i] = true;
      
      balance += mini;
    }
  }
  
  if (balance != 0) {
    cout << "-1";
    return 0;
  }
  
  for (int i = 1; i <= n; ++i) {
    bool is_a = true;
    if (swappedv[i]) is_a = !is_a;
    if (is_max[i]) is_a = !is_a;
    cout << (is_a ? 'A' : 'B');
  }
}

/*
2
42 14 97 89 
30 68 69 53
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 728 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 732 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 788 KB Output is correct
14 Correct 1 ms 1112 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 724 KB Output is correct
26 Correct 2 ms 716 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 728 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 604 KB Output is correct

Subtask #2
89.0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 728 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 732 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 788 KB Output is correct
14 Correct 1 ms 1112 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 724 KB Output is correct
26 Correct 2 ms 716 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 728 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 200 ms 81240 KB Output is correct
35 Correct 249 ms 86724 KB Output is correct
36 Correct 219 ms 83648 KB Output is correct
37 Correct 224 ms 86116 KB Output is correct
38 Correct 240 ms 94884 KB Output is correct
39 Correct 211 ms 82184 KB Output is correct
40 Correct 225 ms 91980 KB Output is correct
41 Correct 214 ms 78932 KB Output is correct
42 Correct 224 ms 80904 KB Output is correct
43 Correct 242 ms 91568 KB Output is correct
44 Correct 263 ms 92576 KB Output is correct
45 Correct 261 ms 92352 KB Output is correct
46 Correct 243 ms 99376 KB Output is correct
47 Correct 233 ms 87992 KB Output is correct
48 Correct 240 ms 86456 KB Output is correct
49 Correct 261 ms 91172 KB Output is correct
50 Correct 247 ms 91072 KB Output is correct
51 Correct 257 ms 91416 KB Output is correct
52 Correct 211 ms 80564 KB Output is correct
53 Correct 187 ms 80140 KB Output is correct
54 Correct 185 ms 87480 KB Output is correct
55 Correct 185 ms 88508 KB Output is correct
56 Correct 221 ms 83792 KB Output is correct
57 Correct 218 ms 78416 KB Output is correct
58 Correct 243 ms 78920 KB Output is correct
59 Correct 201 ms 78808 KB Output is correct
60 Correct 204 ms 74344 KB Output is correct
61 Correct 239 ms 79176 KB Output is correct
62 Correct 207 ms 78164 KB Output is correct
63 Correct 209 ms 79300 KB Output is correct
64 Correct 204 ms 76520 KB Output is correct
65 Correct 213 ms 79296 KB Output is correct