Submission #258784

#	Time	Username	Problem	Language	Result	Execution time	Memory
258784		amoo_safar	Building 4 (JOI20_building4)	C++17	100 / 100	641 ms	50108 KiB

building4

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 1e6 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int n, A[2][N];
int O[2][N];

int mk[N];

int main(){
	scanf("%d", &n);
	n += n;
	for(int it = 0; it < 2; it ++){
		for(int i = 0; i < n; i++){
			scanf("%d", A[it] + i);
			O[it][i] = true;
		}
	}
	for(int i = 1; i < n; i++){
		for(int lv = 0; lv < 2; lv ++){
			O[lv][i] &= (A[0][i - 1] <= A[lv][i] && O[0][i - 1]) || (A[1][i - 1] <= A[lv][i] && O[1][i - 1]);
		}
	}
	for(int i = n - 2; i >= 0; i--){
		for(int lv = 0; lv < 2; lv ++){
			O[lv][i] &= (A[0][i + 1] >= A[lv][i] && O[0][i + 1]) || (A[1][i + 1] >= A[lv][i] && O[1][i + 1]);
		}
	}

	for(int i = 0; i < n; i++)
		if(!O[0][i] && !O[1][i]) return !printf("-1\n");
	
	int sm = 0;
	for(int i = 0; i < n; i++){
		if(O[0][i] && !O[1][i]) sm ++;
		else if(!O[0][i] && O[1][i]) sm --;
		else {
			if(A[0][i] <= A[1][i]) sm ++;
			else sm --;
		}
	}
	bool flg = false;
	if(sm < 0){
		sm = -sm;
		swap(A[0], A[1]);
		swap(O[0], O[1]);
		flg = true;
	}
	int po = 0;
	int Sm = 0;
	vector<pll> V;
	
	//cerr << "# " << sm << '\n';
	
	for(int i = 0; i < n; ){
		if(O[0][i] && !O[1][i]){
			po ++; i = po; continue;
		}
		if(!O[0][i] && O[1][i]){
			po ++; i = po; continue;
		}
		while((po + 1 < n) && (O[0][po + 1] && O[1][po + 1]) && (max(A[0][po], A[1][po]) > min(A[0][po + 1], A[1][po + 1])) ) po ++;
		

		//cerr << "! " << i << ' ' << po << '\n';
		int nw = 0, mn = 0, v, idx = po + 1;
		for(int j = po; j >= i; j--){
			v = (A[0][j] == A[1][j] ? (flg ? -1 : +1) : (A[0][j] < A[1][j] ? +1 : -1) );
			nw -= 2 * v;
			if(nw < mn){
				idx = j;
				mn = nw;
			}
		}
		if(mn < 0){
			Sm += mn;
			V.pb({po, idx});
		}
		po ++;
		i = po;
	}
	//cerr << Sm << '\n';
	if(Sm + sm > 0) return !printf("-1\n");
	//debug(V.size());
	for(auto [P, i] : V){
		int v;
		for(int j = P; j >= i; j--){
			if(sm == 0) break;
			v = (A[0][j] == A[1][j] ? (flg ? -1 : +1) : (A[0][j] < A[1][j] ? +1 : -1) );
			sm -= 2 * v;
			mk[j] = 1;
		}
	}
	if(flg){
		swap(A[0], A[1]);
		swap(O[0], O[1]);
	}
	int out = 0;
	vector<int> I;
	for(int i = 0; i < n; i++){
		//if(mk[i]) debug(i);
		int mn;
		if(!O[0][i]) mn = 1;
		else if(!O[1][i]) mn = 0; 
		else mn = (A[0][i] <= A[1][i] ? 0 : 1);
		if(mk[i]) mn = 1 - mn;
		if(mn == 0) out ++, printf("A");
		if(mn == 1) out --, printf("B");
		I.pb(A[mn][i]);
	}
	for(int i = 0; i + 1 < n; i++) assert(I[i] <= I[i + 1]);
	assert(out == 0);
	printf("\n");
	return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
building4.cpp:32:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", A[it] + i);
    ~~~~~^~~~~~~~~~~~~~~~~

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