Codeforces Round #686 (Div. 3) Editorial

Revision en1, by vovuh, 2020-11-24 22:20:20

1454A - Special Permutation

Idea: MikeMirzayanov

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 0; i < n; ++i) {
			cout << (i + 1) % n + 1 << " ";
		}
		cout << endl;
	}
	
	return 0;
}

1454B - Unique Bid Auction

Idea: MikeMirzayanov

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> cnt(n + 1), idx(n + 1);
		for (int i = 0; i < n; ++i) {
			int x;
			cin >> x;
			++cnt[x];
			idx[x] = i + 1;
		}
		int ans = -1;
		for (int i = 0; i <= n; ++i) {
			if (cnt[i] == 1) {
				ans = idx[i];
				break;
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

1454C - Sequence Transformation

Idea: MikeMirzayanov

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		vector<int> res(n + 1, 1);
		n = unique(a.begin(), a.end()) - a.begin();
		a.resize(n);
		for (int i = 0; i < n; ++i) {
			res[a[i]] += 1;
		}
		res[a[0]] -= 1;
		res[a[n - 1]] -= 1;
		int ans = 1e9;
		for (int i = 0; i < n; ++i) {
			ans = min(ans, res[a[i]]);
		}
		cout << ans << endl;
	}
	
	return 0;
}

1454D - Number into Sequence

Idea: MikeMirzayanov

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		long long n;
		cin >> n;
	
		vector<pair<int, long long>> val;
		for (long long i = 2; i * i <= n; ++i) {
			int cnt = 0;
			while (n % i == 0) {
				++cnt;
				n /= i;
			}
			if (cnt > 0) {
				val.push_back({cnt, i});
			}
		}
		if (n > 1) {
			val.push_back({1, n});
		}
	
		sort(val.rbegin(), val.rend());
		vector<long long> ans(val[0].first, val[0].second);
		for (int i = 1; i < int(val.size()); ++i) {
			for (int j = 0; j < val[i].first; ++j) {
				ans.back() *= val[i].second;
			}
		}
	
		cout << ans.size() << endl;
		for (auto it : ans) cout << it << " ";
		cout << endl;
	}
	
	return 0;
}

1454E - Number of Simple Paths

Idea: vovuh

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<set<int>> g(n);
		for (int i = 0; i < n; ++i) {
			int x, y;
			cin >> x >> y;
			--x, --y;
			g[x].insert(y);
			g[y].insert(x);
		}
		vector<int> val(n, 1);
		queue<int> leafs;
		for (int i = 0; i < n; ++i) {
			if (g[i].size() == 1) {
				leafs.push(i);
			}
		}
		while (!leafs.empty()) {
			int v = leafs.front();
			leafs.pop();
			int to = *g[v].begin();
			val[to] += val[v];
			val[v] = 0;
			g[v].clear();
			g[to].erase(v);
			if (g[to].size() == 1) {
				leafs.push(to);
			}
		}
		long long ans = 0;
		for (int i = 0; i < n; ++i) {
			ans += val[i] * 1ll * (val[i] - 1) / 2;
			ans += val[i] * 1ll * (n - val[i]);
		}
		cout << ans << endl;
	}
	
	return 0;
}

1454F - Array Partition

Idea: MikeMirzayanov

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

bool found;

void shift(multiset<int> &l, multiset<int> &r, int val) {
	l.erase(l.find(val));
	r.insert(val);
}

void check(const multiset<int> &lf, const multiset<int> &mid, const multiset<int> &rg) {
	if (found || lf.empty() || mid.empty() || rg.empty()) {
		return;
	}
	if (*lf.rbegin() == *mid.begin() && *mid.begin() == *rg.rbegin()) {
		found = true;
		cout << "YES" << endl;
		cout << lf.size() << " " << mid.size() << " " << rg.size() << endl;
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		
		found = false;
		multiset<int> lf, mid(a.begin(), a.end()), rg;
		int r = n - 1;
		for (int l = 0; l < n - 2; ++l) {
			shift(mid, lf, a[l]);
			while (r - 1 >= l && a[r] <= *lf.rbegin()) {
				shift(mid, rg, a[r]);
				--r;
			}
			
			while (r - 1 < l) {
				shift(rg, mid, a[r + 1]);
				++r;
			}
			
			check(lf, mid, rg);
			
			shift(lf, mid, a[l]);
			check(lf, mid, rg);
			shift(mid, lf, a[l]);
			
			if (rg.empty()) continue;
			
			shift(rg, mid, a[r + 1]);
			check(lf, mid, rg);
			shift(mid, rg, a[r + 1]);
		}
		if (!found) {
			cout << "NO" << endl;
		}
	}
	
	return 0;
}
Solution (Gassa)
// Author: Ivan Kazmenko (gassa@mail.ru)
module solution;
import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;

void main ()
{
	auto tests = readln.strip.to !(int);
	foreach (test; 0..tests)
	{
		auto n = readln.strip.to !(int);
		auto a = readln.splitter.map !(to !(int)).array;
		auto x = a.dup;
		foreach (i; 1..n)
		{
			x[i] = max (x[i], x[i - 1]);
		}
		auto y = a.dup;
		foreach_reverse (i; 0..n - 1)
		{
			y[i] = max (y[i], y[i + 1]);
		}

		auto v = a.maxElement;
		auto maxPlaces = n.iota.filter !(i => a[i] == v).array;
		int lo = maxPlaces[$ / 2];
		int hi = lo + 1;

		while (true)
		{
			if (lo == 0 || hi == n)
			{
				writeln ("NO");
				break;
			}
			if (x[lo - 1] == v && y[hi] == v)
			{
				writeln ("YES");
				writeln (lo, " ", hi - lo, " ", n - hi);
				break;
			}
			int u = (lo - 1 == 0) ? int.min :
			    min (x[lo - 2], a[lo - 1]);
			int w = (hi + 1 >= n) ? int.min :
			    min (y[hi + 1], a[hi]);
			if (u > w)
			{
				v = min (v, a[lo - 1]);
				lo -= 1;
			}
			else
			{
				v = min (v, a[hi]);
				hi += 1;
			}
		}
	}
}
Tags codeforces, 686, third division, editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian vovuh 2020-11-24 22:21:50 7026 Первая редакция перевода на Русский
en1 English vovuh 2020-11-24 22:20:20 7048 Initial revision (published)