Submission #238394

#	Time	Username	Problem	Language	Result	Execution time	Memory
238394		Retro3014	건물 4 (JOI20_building4)	C++17	100 / 100	448 ms	40568 KiB

building4

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 1000000;

int N;
pii arr[2][MAX_N+1];
int num[MAX_N+1];
int A[MAX_N+1], B[MAX_N+1];
int cost[MAX_N+1];
int chk[MAX_N+1];
int num2[MAX_N+1];

int main(){
	scanf("%d", &N);
	N*=2;
	int sum = 0, prv = 0;
	for(int i=1; i<=N; i++)	scanf("%d", &A[i]);
	for(int i=1; i<=N; i++)	scanf("%d", &B[i]);
	for(int i=1; i<=N; i++){
		int a=A[i], b=B[i];
		if(a<b){
			arr[0][i] = {a, 1};
			arr[1][i] = {b, -1};
		}else{
			arr[0][i] = {b, -1};
			arr[1][i] = {a, 1};
		}
		if(arr[0][i].first<prv){
			if(arr[1][i].first<prv){
				printf("-1");
				return 0;
			}
			prv = arr[1][i].first;
			sum+=arr[1][i].second;
			num[i] = 1;
		}else{
			prv = arr[0][i].first;
			sum+=arr[0][i].second;
			num[i] = 0;
		}
	}
	prv = INF;
	for(int i=N; i>=1; i--){
		if(num[i]==0){
			if(prv>=arr[1][i].first){
				if((sum<0 && arr[0][i].second<0) || (sum>0 && arr[0][i].second>0)){
					num[i] = 1;
					sum+=2*arr[1][i].second;
				}else{
					cost[i] = 2*arr[1][i].second;
					num2[i] = 1;
				}
			}else{
				if(i!=N && num[i+1]==0){
					if(arr[1][i+1].first>=arr[1][i].first){
						if(num2[i+1]==-1){
							num2[i] = -1;
						}else{
							num2[i] = num2[i+1]+1;
							cost[i] = cost[i+1] + 2*arr[1][i].second;
							if((sum>0 && cost[i]<0) || (sum<0 && cost[i]>0)){
								sum+=cost[i];
								num[i] = 1;
								chk[i] = num2[i]-1;
							}
						}
					}else{
						num2[i] = -1;
					}
				}else{
					num2[i] = -1;
				}
			}
		}
		prv = arr[num[i]][i].first;
	}
	if(sum==0){
		int mn = 0;
		for(int i=1; i<=N; i++){
			if(i<=mn){
				num[i] = 1-num[i];
			}
			if(arr[num[i]][i].second==1){
				printf("A");
			}else{
				printf("B");
			}
			mn = max(mn, i+chk[i]);
		}
	}else{
		printf("-1");
	}
	return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
building4.cpp:39:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
                          ~~~~~^~~~~~~~~~~~~
building4.cpp:40:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%d", &B[i]);
                          ~~~~~^~~~~~~~~~~~~

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