oj.uz

Submission #424547

# Submission time Handle Problem Language Result Execution time Memory
424547 2021-06-12T05:21:37 Z juggernaut Building 4 (JOI20_building4) C++17
100 / 100
 432 ms 27372 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 448 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 3 ms 440 KB Output is correct
19 Correct 3 ms 460 KB Output is correct
20 Correct 3 ms 460 KB Output is correct
21 Correct 2 ms 444 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 3 ms 460 KB Output is correct
24 Correct 2 ms 448 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 2 ms 460 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 1 ms 460 KB Output is correct
33 Correct 2 ms 460 KB Output is correct

Subtask #2
89.0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 448 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 3 ms 440 KB Output is correct
19 Correct 3 ms 460 KB Output is correct
20 Correct 3 ms 460 KB Output is correct
21 Correct 2 ms 444 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 3 ms 460 KB Output is correct
24 Correct 2 ms 448 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 2 ms 460 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 1 ms 460 KB Output is correct
33 Correct 2 ms 460 KB Output is correct
34 Correct 306 ms 25480 KB Output is correct
35 Correct 354 ms 25100 KB Output is correct
36 Correct 349 ms 24620 KB Output is correct
37 Correct 368 ms 25192 KB Output is correct
38 Correct 338 ms 25156 KB Output is correct
39 Correct 325 ms 25820 KB Output is correct
40 Correct 363 ms 26816 KB Output is correct
41 Correct 333 ms 25576 KB Output is correct
42 Correct 364 ms 26092 KB Output is correct
43 Correct 379 ms 27032 KB Output is correct
44 Correct 364 ms 26960 KB Output is correct
45 Correct 432 ms 27036 KB Output is correct
46 Correct 345 ms 27012 KB Output is correct
47 Correct 326 ms 26964 KB Output is correct
48 Correct 362 ms 27000 KB Output is correct
49 Correct 351 ms 26900 KB Output is correct
50 Correct 363 ms 27008 KB Output is correct
51 Correct 416 ms 26960 KB Output is correct
52 Correct 277 ms 26780 KB Output is correct
53 Correct 281 ms 26912 KB Output is correct
54 Correct 265 ms 26928 KB Output is correct
55 Correct 283 ms 26816 KB Output is correct
56 Correct 382 ms 27048 KB Output is correct
57 Correct 324 ms 27176 KB Output is correct
58 Correct 293 ms 27344 KB Output is correct
59 Correct 314 ms 27340 KB Output is correct
60 Correct 321 ms 25884 KB Output is correct
61 Correct 307 ms 27332 KB Output is correct
62 Correct 292 ms 26988 KB Output is correct
63 Correct 351 ms 27288 KB Output is correct
64 Correct 338 ms 26388 KB Output is correct
65 Correct 324 ms 27372 KB Output is correct