oj.uz

Submission #396876

# Submission time Handle Problem Language Result Execution time Memory
396876 2021-04-30T21:42:15 Z AmineWeslati Building 4 (JOI20_building4) C++14
11 / 100
 886 ms 524288 KB 
//Never stop trying
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 2000 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}
#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////

int N;
vi A(MX*2),B(MX*2);

int memo[MX*8][MX][2][2];

int solve(int l, int r, int n, int b, int e, int pos){
	if(n>(r-l+1)) return 0;
	if(n<(b==0)+(l<r && e==0)) return 0;
	if(l==r){
		if(b!=e) return 0;
		if(n && b) return 0;
		if(!n && !b) return 0;
		return 1;
	}

	int &ind=memo[pos][n][b][e];
	if(ind!=-1) return ind;

	FOR(n1,0,n+1) FOR(e1,0,2) FOR(b2,0,2){
		int b1=b,e2=e;

		int n2=n-n1,m=(l+r)/2;

		int x=A[m]; if(e1) x=B[m];
		int y=A[m+1]; if(b2) y=B[m+1];

		if(x<=y && solve(l,m,n1,b1,e1,pos*2) && 
			solve(m+1,r,n2,b2,e2,pos*2+1))
				return ind=1;
	}
	return ind=0;
}

str build(int l, int r, int n, int b, int e, int pos){
	if(l==r){
		if(!b) return "A"; 
		return "B";
	}

	FOR(n1,0,n+1) FOR(e1,0,2) FOR(b2,0,2){
		int b1=b,e2=e;

		int n2=n-n1,m=(l+r)/2;

		int x=A[m]; if(e1) x=B[m];
		int y=A[m+1]; if(b2) y=B[m+1];

		if(x<=y && solve(l,m,n1,b1,e1,pos*2) && 
			solve(m+1,r,n2,b2,e2,pos*2+1)){
				str ans=build(l,m,n1,b1,e1,pos*2);
				ans+=build(m+1,r,n2,b2,e2,pos*2+1);
				return ans; 
			}
	}
	return "";
}

int main() {
    boost; IO();
    
    cin>>N;
    FOR(i,0,N*2) cin>>A[i];
    FOR(i,0,N*2) cin>>B[i];

    memset(memo,-1,sizeof(memo));
   	FOR(b,0,2) FOR(e,0,2){
   		if(solve(0,2*N-1,N,b,e,1)){
   			cout << build(0,2*N-1,N,b,e,1) << endl;
   			return 0;
   		}
   	}

   	cout << -1 << endl;
   	//cout << solve(0,2*N-1,N,1,0,1) << endl;

    return 0;
}
//Change your approach

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 506328 KB Output is correct
2 Correct 228 ms 506348 KB Output is correct
3 Correct 232 ms 506308 KB Output is correct
4 Correct 228 ms 506340 KB Output is correct
5 Correct 229 ms 506316 KB Output is correct
6 Correct 569 ms 506428 KB Output is correct
7 Correct 437 ms 506436 KB Output is correct
8 Correct 293 ms 506416 KB Output is correct
9 Correct 727 ms 506408 KB Output is correct
10 Correct 412 ms 506424 KB Output is correct
11 Correct 345 ms 506308 KB Output is correct
12 Correct 342 ms 506356 KB Output is correct
13 Correct 567 ms 506408 KB Output is correct
14 Correct 294 ms 506436 KB Output is correct
15 Correct 725 ms 506416 KB Output is correct
16 Correct 613 ms 506432 KB Output is correct
17 Correct 563 ms 506464 KB Output is correct
18 Correct 587 ms 506436 KB Output is correct
19 Correct 741 ms 506452 KB Output is correct
20 Correct 654 ms 506432 KB Output is correct
21 Correct 614 ms 506452 KB Output is correct
22 Correct 283 ms 506304 KB Output is correct
23 Correct 333 ms 506480 KB Output is correct
24 Correct 313 ms 506416 KB Output is correct
25 Correct 683 ms 506372 KB Output is correct
26 Correct 688 ms 506308 KB Output is correct
27 Correct 792 ms 506376 KB Output is correct
28 Correct 392 ms 506308 KB Output is correct
29 Correct 415 ms 506500 KB Output is correct
30 Correct 426 ms 506372 KB Output is correct
31 Correct 443 ms 506420 KB Output is correct
32 Correct 529 ms 506424 KB Output is correct
33 Correct 658 ms 506380 KB Output is correct

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 506328 KB Output is correct
2 Correct 228 ms 506348 KB Output is correct
3 Correct 232 ms 506308 KB Output is correct
4 Correct 228 ms 506340 KB Output is correct
5 Correct 229 ms 506316 KB Output is correct
6 Correct 569 ms 506428 KB Output is correct
7 Correct 437 ms 506436 KB Output is correct
8 Correct 293 ms 506416 KB Output is correct
9 Correct 727 ms 506408 KB Output is correct
10 Correct 412 ms 506424 KB Output is correct
11 Correct 345 ms 506308 KB Output is correct
12 Correct 342 ms 506356 KB Output is correct
13 Correct 567 ms 506408 KB Output is correct
14 Correct 294 ms 506436 KB Output is correct
15 Correct 725 ms 506416 KB Output is correct
16 Correct 613 ms 506432 KB Output is correct
17 Correct 563 ms 506464 KB Output is correct
18 Correct 587 ms 506436 KB Output is correct
19 Correct 741 ms 506452 KB Output is correct
20 Correct 654 ms 506432 KB Output is correct
21 Correct 614 ms 506452 KB Output is correct
22 Correct 283 ms 506304 KB Output is correct
23 Correct 333 ms 506480 KB Output is correct
24 Correct 313 ms 506416 KB Output is correct
25 Correct 683 ms 506372 KB Output is correct
26 Correct 688 ms 506308 KB Output is correct
27 Correct 792 ms 506376 KB Output is correct
28 Correct 392 ms 506308 KB Output is correct
29 Correct 415 ms 506500 KB Output is correct
30 Correct 426 ms 506372 KB Output is correct
31 Correct 443 ms 506420 KB Output is correct
32 Correct 529 ms 506424 KB Output is correct
33 Correct 658 ms 506380 KB Output is correct
34 Runtime error 886 ms 524288 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -