Submission #212538

#	Time	Username	Problem	Language	Result	Execution time	Memory
212538		antonis	Building 4 (JOI20_building4)	C++14	0 / 100	8 ms	512 KiB

building4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef tuple<int, int, int, int> tiiii;
typedef set <int> si;
typedef map <int, int> mii;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <vector <int>> vvi;  
#define F(i, a, b) for(int i = a; i <= (int)b; i++)
#define f(i, a, b) for(int i = a; i >= (int)b; i--)
#define F2(i, a, b) for(int i = a; i <= (int)b; i+=2)
#define f2(i, a, b) for(int i = a; i >= (int)b; i-=2)
#define wh(n) int iteration = n; while(iteration--) 
#define For(t, it) for(auto it = (t).begin(); it != (t).end(); ++it)
#define IN insert
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define RS resize
#define uset unordered_set
#define umap unordered_map
#define GRAF(n) vvi gr; gr.resize(n+1); vector <bool> was(n+1, 0);
ld const PI = acos(-1);

int const N = 1e6 + 7, inf = 1e9 + 7;
int a[2][N], ans[N], cnt[2];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
        #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
	#endif
	int n;
	cin >> n;
	F(i, 0, 1)
		F(j, 1, 2*n)
			cin >> a[i][j];
	ans[0] = a[0][0] = 0;
	ans[2*n+1] = 0, a[0][2*n+1] = inf;
	F(i, 1, 2*n){
	        int mx = inf, pos = -1;
		F(j, 0, 1)
			if(a[j][i] >= a[ans[i-1]][i-1] && a[j][i] < mx)
				mx = a[j][i], pos = j;
		if(pos == -1){
			cout << -1;
			return 0;
		}
		ans[i] = pos;
		cnt[pos]++;	
	}
	f(i, 2*n, 1){
		if(cnt[ans[i]] <= n)
			continue;
		if(a[!ans[i]][i] >= a[ans[i]][i] && a[!ans[i]][i] <= a[ans[i+1]][i+1]){
			cnt[ans[i]]--;
			ans[i] ^= 1;
			cnt[ans[i]]++;
		}
	} 
	if(cnt[0] != cnt[1]){
		cout << -1;
		return 0;
	}
	F(i, 1, 2*n)
		cout << char('A' + ans[i]);
	return 0;
}

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