Mail.Ru Cup 2018 Round 1 wu-kan

Elevator or Stairs?

#include <bits/stdc++.h>
using namespace std;
int x, y, z, t1, t2, t3;
int main()
{
	scanf("%d%d%d%d%d%d", &x, &y, &z, &t1, &t2, &t3);
	printf(abs(z - x) * t2 + abs(x - y) * t2 + 3 * t3 <= t1 * abs(x - y) ? "YES" : "NO");
}

Appending Mex

每一步能得到的值是0,1,...,m+1,其中m是前几步得到的最大的数。

#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
	scanf("%d", &n);
	for (int i = 1, m = -1, a; i <= n; ++i)
	{
		scanf("%d", &a);
		if (a > m + 1)
			return printf("%d", i), 0;
		m = max(m, a);
	}
	printf("-1");
}

Candies Distribution

l[i]+r[i]之后在所有数里的排名就是原来的排名,回代检验即可。

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int N = 1023;
struct Ranker : vector<ll>
{
	void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
	int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
} rk;
int n, l[N], r[N], a[N];
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &l[i]);
	for (int i = 0; i < n; ++i)
		scanf("%d", &r[i]), rk.push_back(l[i] + r[i]);
	rk.init();
	for (int i = 0; i < n; ++i)
	{
		a[i] = n - rk.ask(l[i] + r[i]);
		for (int j = 0; j < i; ++j)
		{
			l[i] -= a[i] < a[j];
			r[j] -= a[j] < a[i];
		}
	}
	for (int i = 0; i < n; ++i)
		if (l[i] || r[i])
			return printf("NO"), 0;
	printf("YES\n");
	for (int i = 0; i < n; ++i)
		printf("%d ", a[i]);
}

Changing Array

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, ans;
unordered_map<ll, ll> mp{{0, 1}};
int main()
{
	scanf("%lld%lld", &n, &k);
	for (ll i = 1, a = 0, s = 0; i <= n; ++i)
	{
		scanf("%d", &a);
		ll &x = mp[s ^= a], &y = mp[s ^ ((1LL << k) - 1)];
		ans += i - (x < y ? x++ : y++);
	}
	printf("%lld", ans);
}