Submission #211501

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
211501	2020-03-20 15:50:22	Pajaraja	Building 4 (JOI20_building4)	C++17	100 / 100	425 ms	27780 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>
#define MAXN 500007
using namespace std;
int mn[2][2*MAXN],mx[2][2*MAXN],a[2][2*MAXN];
bool mz[2][2*MAXN];
char rc[2*MAXN];
void reconstruct(int k,int ind,int val)
{
  rc[ind]='A'+k;
  if(!ind) return;
  for(int t=0;t<2;t++) if(a[t][ind-1]<=a[k][ind] && mn[t][ind-1]<=val-k && mx[t][ind-1]>=val-k) {reconstruct(t,ind-1,val-k); return;}
}
int main()
{
  int n;
  scanf("%d",&n);
  for(int i=0;i<2*n;i++) scanf("%d",&a[0][i]);
  for(int i=0;i<2*n;i++) scanf("%d",&a[1][i]);
  mz[0][0]=mz[1][0]=true;
  mn[0][0]=mx[0][0]=0;
  mn[1][0]=mx[1][0]=1;
  for(int i=1;i<2*n;i++) mn[0][i]=mn[1][i]=2*n+12;
  for(int i=1;i<2*n;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) if(a[k][i-1]<=a[j][i] && mz[k][i-1]) 
  {
    mz[j][i]=true; 
    mn[j][i]=min(mn[j][i],mn[k][i-1]+j);
    mx[j][i]=max(mx[j][i],mx[k][i-1]+j);
  }
  for(int t=0;t<2;t++) if(mn[t][2*n-1]<=n && mx[t][2*n-1]>=n && mz[t][2*n-1])
  {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
building4.cpp:17:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<2*n;i++) scanf("%d",&a[0][i]);
                         ~~~~~^~~~~~~~~~~~~~~
building4.cpp:18:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<2*n;i++) scanf("%d",&a[1][i]);
                         ~~~~~^~~~~~~~~~~~~~~

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