Submission #483167

#	Time	Username	Problem	Language	Result	Execution time	Memory
483167		jamezzz	Building 4 (JOI20_building4)	C++17	100 / 100	291 ms	45216 KiB

building4

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define maxn 1000005

int n,a[maxn][2],mn[maxn][2],mx[maxn][2];
vector<char> ans;

int main(){
	sf("%d",&n);n*=2;
	for(int i=0;i<n;++i)sf("%d",&a[i][0]);
	for(int i=0;i<n;++i)sf("%d",&a[i][1]);
	a[n][0]=a[n][1]=INF;
	for(int i=n-1;i>=0;--i){
		for(int j=0;j<2;++j){
			mn[i][j]=INF;
			mx[i][j]=-INF;
			if(a[i][j]<=a[i+1][0]){
				mnto(mn[i][j],mn[i+1][0]+(j==0));
				mxto(mx[i][j],mx[i+1][0]+(j==0));
			}
			if(a[i][j]<=a[i+1][1]){
				mnto(mn[i][j],mn[i+1][1]+(j==0));
				mxto(mx[i][j],mx[i+1][1]+(j==0));
			}
		}
	}
	int rem=n/2,cur=-1;
	for(int i=0;i<n;++i){
		if((mn[i][0]<=rem&&rem<=mx[i][0])&&(cur==-1||a[i-1][cur]<=a[i][0])){
			ans.pb('A');cur=0;--rem;
		}
		else if((mn[i][1]<=rem&&rem<=mx[i][1])&&(cur==-1||a[i-1][cur]<=a[i][1])){
			ans.pb('B');cur=1;
		}
		else{
			pf("-1\n");exit(0);
		}
	}
	for(int i=0;i<n;++i)pf("%c",ans[i]);
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:37:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  sf("%d",&n);n*=2;
      |    ^
building4.cpp:38:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  for(int i=0;i<n;++i)sf("%d",&a[i][0]);
      |                        ^
building4.cpp:39:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  for(int i=0;i<n;++i)sf("%d",&a[i][1]);
      |                        ^

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