oj.uz

답안 #707359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
707359 2023-03-08T21:20:37 Z urosk 건물 4 (JOI20_building4) C++14
100 / 100
 276 ms 67788 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
//using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
*/
#define maxn 1000005
ll n;
ll a[maxn],b[maxn];
pll dpa[maxn],dpb[maxn];
void tc(){
    cin >> n;
    n*=2;
    for(ll i = 1;i<=n;i++) cin >> a[i];
    for(ll i = 1;i<=n;i++) cin >> b[i];
    dpa[n] = {1,1};
    dpb[n] = {0,0};
    for(ll i = n-1;i>=1;i--){
        dpa[i] = dpb[i] = {n,-n};
        if(a[i]<=a[i+1]){
            dpa[i].fi = min(dpa[i].fi,dpa[i+1].fi+1);
            dpa[i].sc = max(dpa[i].sc,dpa[i+1].sc+1);
        }
        if(a[i]<=b[i+1]){
            dpa[i].fi = min(dpa[i].fi,dpb[i+1].fi+1);
            dpa[i].sc = max(dpa[i].sc,dpb[i+1].sc+1);
        }
        if(b[i]<=a[i+1]){
            dpb[i].fi = min(dpb[i].fi,dpa[i+1].fi);
            dpb[i].sc = max(dpb[i].sc,dpa[i+1].sc);
        }
        if(b[i]<=b[i+1]){
            dpb[i].fi = min(dpb[i].fi,dpb[i+1].fi);
            dpb[i].sc = max(dpb[i].sc,dpb[i+1].sc);
        }
    }
    bool oka = 1,okb = 1;
    if(dpa[1].fi>n/2||dpa[1].sc<n/2) oka = 0;
    if(dpb[1].fi>n/2||dpb[1].sc<n/2) okb = 0;
    if(!oka&&!okb){cout<<-1<<endl;return;}
    ll x = 0,cnt = n/2;
    for(ll i = 1;i<=n;i++){
        if(x<=a[i]&&dpa[i].fi<=cnt&&dpa[i].sc>=cnt){
            cout<<'A';
            x = a[i];
            cnt--;
        }else{
            cout<<'B';
            x = b[i];
        }
    }
    cout<<endl;
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}
/**
3
2 5 4 9 15 11
6 7 6 8 12 14
**/

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 532 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 540 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct

Subtask #2
89.0 / 89.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 532 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 540 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 209 ms 65504 KB Output is correct
35 Correct 212 ms 62668 KB Output is correct
36 Correct 211 ms 61672 KB Output is correct
37 Correct 221 ms 62924 KB Output is correct
38 Correct 203 ms 62924 KB Output is correct
39 Correct 204 ms 62164 KB Output is correct
40 Correct 217 ms 66920 KB Output is correct
41 Correct 206 ms 63564 KB Output is correct
42 Correct 219 ms 65352 KB Output is correct
43 Correct 230 ms 67544 KB Output is correct
44 Correct 236 ms 67548 KB Output is correct
45 Correct 230 ms 67588 KB Output is correct
46 Correct 215 ms 67544 KB Output is correct
47 Correct 224 ms 66576 KB Output is correct
48 Correct 216 ms 66472 KB Output is correct
49 Correct 222 ms 67304 KB Output is correct
50 Correct 231 ms 66764 KB Output is correct
51 Correct 276 ms 66644 KB Output is correct
52 Correct 170 ms 55856 KB Output is correct
53 Correct 179 ms 55812 KB Output is correct
54 Correct 147 ms 55760 KB Output is correct
55 Correct 156 ms 55520 KB Output is correct
56 Correct 217 ms 67788 KB Output is correct
57 Correct 187 ms 62508 KB Output is correct
58 Correct 189 ms 62820 KB Output is correct
59 Correct 191 ms 62792 KB Output is correct
60 Correct 181 ms 59428 KB Output is correct
61 Correct 203 ms 63240 KB Output is correct
62 Correct 189 ms 62280 KB Output is correct
63 Correct 194 ms 63188 KB Output is correct
64 Correct 192 ms 61108 KB Output is correct
65 Correct 199 ms 63264 KB Output is correct