Submission #1113922

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1113922	2024-11-17 19:58:33	Dan4Life	Building 4 (JOI20_building4)	C++17	0 / 100	3 ms	12624 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];
int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> n;
  for(int i = 0; i < 2*n; i++) cin >> a[0][i];
  for(int i = 0; i < 2*n; i++) cin >> a[1][i];
  // dp i j k:   i= min/max As used  j = placed A/B here, till kth index
  dp[0][0][0] = 1;
  dp[1][0][0] = 1;
  dp[0][1][0] = 0;
  dp[1][1][0] = 0;
  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 = (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++) 
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

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

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