Submission #550826

#	Time	Username	Problem	Language	Result	Execution time	Memory
550826		MilosMilutinovic	건물 4 (JOI20_building4)	C++14	100 / 100	384 ms	45264 KiB

building4

//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=1000*1007;

int n;
int tab[nax][2];

int dpl[nax][2];
int dpr[nax][2];

char ans[nax];

void no()
{
	printf("-1");
	exit(0);
}
void check()
{
	int pre=0;
	for (int i=1; i<=n; i++)
	{
		int wzn=1e9+5;
		for (int j=0; j<2; j++)
			if (tab[i][j]>=pre)
				wzn=min(wzn, tab[i][j]);
		if (wzn>1e9)
			no();
		pre=wzn;
	}
}
void rec(int i, int sl, int jos)
{
	ans[i]='A'+sl;
	jos-=(sl==1);
	if (i==1)
	{
		assert(jos==0);
		return;
	}
	for (int j=0; j<2; j++)
		if (tab[i][sl]>=tab[i-1][j] && dpl[i-1][j]<=jos && dpr[i-1][j]>=jos)
		{
			rec(i-1, j, jos);
			break;
		}
}
int main()
{
	scanf("%d", &n);
	n=2*n;
	for (int i=1; i<=n; i++)
		scanf("%d", &tab[i][0]);
	for (int i=1; i<=n; i++)
		scanf("%d", &tab[i][1]);
	check();
	for (int i=1; i<=n; i++)
		for (int j=0; j<2; j++)
			dpl[i][j]=1e9, dpr[i][j]=-1e9;
	dpl[1][0]=0;
	dpr[1][0]=0;
	dpl[1][1]=1;
	dpr[1][1]=1;
	for (int i=2; i<=n; i++)
		for (int x=0; x<2; x++)
			for (int y=0; y<2; y++)
			{
				if (tab[i-1][x]>tab[i][y])
					continue;
				dpl[i][y]=min(dpl[i][y], dpl[i-1][x]+(y==1));
				dpr[i][y]=max(dpr[i][y], dpr[i-1][x]+(y==1));
			}
	int ok=0;
	for (int i=0; i<2; i++)
		if (dpl[n][i]<=n/2 && dpr[n][i]>=n/2)
		{
			rec(n, i, n/2);
			ok=1;
			break;
		}
	if (ok==0)
		no();
	for (int i=1; i<=n; i++)
		printf("%c", ans[i]);
	return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
building4.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   scanf("%d", &tab[i][0]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
building4.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |   scanf("%d", &tab[i][1]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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