Submission #211690

#	Time	Username	Problem	Language	Result	Execution time	Memory
211690		skylee	Building 4 (JOI20_building4)	C++17	100 / 100	297 ms	60996 KiB

building4

#include<cstdio>
#include<cctype>
#include<climits>
#include<cstring>
#include<algorithm>
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
using int64=long long;
constexpr int N=1e6+1;
int v[N][2];
int f[N][2][2],g[N][2][2];
char s[N];
int main() {
	const int n=getint()*2;
	for(register int i=1;i<=n;i++) v[i][0]=getint();
	for(register int i=1;i<=n;i++) v[i][1]=getint();
	for(register int i=1;i<=n;i++) {
		for(register int j=0;j<2;j++) {
			for(register int k=0;k<2;k++) {
				const int l=std::min(f[i-1][k][0],f[i-1][k][1]);
				const int r=std::max(g[i-1][k][0],g[i-1][k][1]);
				if(v[i][j]<v[i-1][k]||l==INT_MAX||r==INT_MIN) {
					f[i][j][k]=INT_MAX;
					g[i][j][k]=INT_MIN;
					continue;
				}
				f[i][j][k]=l+(j?1:-1);
				g[i][j][k]=r+(j?1:-1);
			}
		}
	}
	int num=0;
	int j=std::min(f[n][1][0],f[n][1][1])<=0&&0<=std::max(g[n][1][0],g[n][1][1]);
	for(register int i=n;i>=1;i--) {
		for(register int k=0;k<2;k++) {
			if(f[i][j][k]<=num&&num<=g[i][j][k]) {
				s[i-1]='A'+j;
				num-=j?1:-1;
				j=k;
				break;
			}
		}
	}
	puts((int)strlen(s)==n?s:"-1");
	return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int getint()':
building4.cpp:7:16: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
  register char ch;
                ^~
building4.cpp:9:15: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
  register int x=ch^'0';
               ^
building4.cpp: In function 'int main()':
building4.cpp:20:19: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
  for(register int i=1;i<=n;i++) v[i][0]=getint();
                   ^
building4.cpp:21:19: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
  for(register int i=1;i<=n;i++) v[i][1]=getint();
                   ^
building4.cpp:22:19: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
  for(register int i=1;i<=n;i++) {
                   ^
building4.cpp:23:20: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
   for(register int j=0;j<2;j++) {
                    ^
building4.cpp:24:21: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
    for(register int k=0;k<2;k++) {
                     ^
building4.cpp:39:19: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
  for(register int i=n;i>=1;i--) {
                   ^
building4.cpp:40:20: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
   for(register int k=0;k<2;k++) {
                    ^

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