Submission #424547

#	Time	Username	Problem	Language	Result	Execution time	Memory
424547		juggernaut	Building 4 (JOI20_building4)	C++17	100 / 100	432 ms	27372 KiB

building4

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
typedef long long ll;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef IOI2021SG
    #define printl(args...)printf(args)
#else
    #define printl(args...)((void)0)
#endif
int n;
int a[1000005];
int b[1000005];
int L[1000005][2];
int R[1000005][2];
bool ans[1000005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=(n<<1);i++)scanf("%d",&a[i]);
    for(int i=1;i<=(n<<1);i++)scanf("%d",&b[i]);
    L[1][0]=1;
    L[1][1]=0;
    R[1][0]=1;
    R[1][1]=0;
    for(int i=2;i<=(n<<1);i++){
        L[i][0]=L[i][1]=2e9;
        if(a[i-1]<=a[i])umin(L[i][0],L[i-1][0]+1);
        if(b[i-1]<=a[i])umin(L[i][0],L[i-1][1]+1);

        if(a[i-1]<=b[i])umin(L[i][1],L[i-1][0]);
        if(b[i-1]<=b[i])umin(L[i][1],L[i-1][1]);
        R[i][0]=R[i][1]=-2e9;
        if(a[i-1]<=a[i])umax(R[i][0],R[i-1][0]+1);
        if(b[i-1]<=a[i])umax(R[i][0],R[i-1][1]+1);

        if(a[i-1]<=b[i])umax(R[i][1],R[i-1][0]);
        if(b[i-1]<=b[i])umax(R[i][1],R[i-1][1]);
    }
    if(!((L[n<<1][0]<=n&&n<=R[n<<1][0])||(L[n<<1][1]<=n&&n<=R[n<<1][1])))return puts("-1"),0;
    int last=2e9;
    int A=n;
    for(int i=(n<<1);i>0;i--){
        if(a[i]<=last&&L[i][0]<=A&&A<=R[i][0]){
            last=a[i];
            ans[i]=0;
            A--;
        }else{
            last=b[i];
            ans[i]=1;
        }
    }
    for(int i=1;i<=(n<<1);i++)if(ans[i])printf("B");else printf("A");
}

Compilation message (stderr)

building4.cpp: In function 'void usaco(std::string)':
building4.cpp:5:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building4.cpp:5:66: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building4.cpp: In function 'int main()':
building4.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
building4.cpp:28:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     for(int i=1;i<=(n<<1);i++)scanf("%d",&a[i]);
      |                               ~~~~~^~~~~~~~~~~~
building4.cpp:29:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     for(int i=1;i<=(n<<1);i++)scanf("%d",&b[i]);
      |                               ~~~~~^~~~~~~~~~~~

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