Submission #1113924

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1113924	2024-11-17 20:04:12	Dan4Life	Building 4 (JOI20_building4)	C++17	0 / 100	3 ms	10576 KiB

building4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e6+10;
int n, ans[N], a[2][N], dp[2][2][N];
// dp[i][j][k]: i= min/max As used, j = placed A/B here?, considering till kth index
int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> n; dp[0][0][0] = dp[1][0][0] = 1;
  for(int i = 0; i < 2*n; i++) cin >> a[0][i];
  for(int i = 0; i < 2*n; i++) cin >> a[1][i];
  
  for(int i = 1; i < 2*n; i++)
    dp[0][0][i]=dp[0][1][i]=2*n;
  for(int i = 1; i < 2*n; i++)
    for(int k : {0,1}) for(int j : {0,1})
      if(a[j][i-1] <= a[k][i])
        dp[0][k][i] = min(dp[0][k][i],dp[0][j][i-1]+!k),
        dp[1][k][i] = max(dp[1][k][i],dp[1][j][i-1]+!k);
  for(int k : {0,1}){
    if(dp[0][k][2*n-1]<=n and dp[1][k][2*n-1]>=n){
      ans[2*n-1] = k; int sum = n-!k;
      for(int i = 2*n-2; i>=0; i--){
        int cur = (!sum or dp[0][0][i]>sum or dp[1][0][i]<sum or dp[0][0][i]>dp[1][0][i]);
        ans[i]=cur; sum-=!cur;
      }
      for(int i = 0; i < 2*n; i++) 
        cout << "AB"[ans[i]]; cout << "\n";
      return 0;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:27:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   27 |    for(int i = 0; i < 2*n; i++)
      |    ^~~
building4.cpp:28:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   28 |     cout << "AB"[ans[i]]; cout << "\n";
      |                           ^~~~

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