Submission #1113922

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
11139222024-11-17 19:58:33Dan4LifeBuilding 4 (JOI20_building4)C++17
0 / 100
3 ms12624 KiB
#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";
      |                           ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...