Submission #111297

#	Time	Username	Problem	Language	Result	Execution time	Memory
111297		atoiz	Alternating Current (BOI18_alternating)	C++14	100 / 100	46 ms	4588 KiB

alternating

/*input
5 4
1 3
2 4
4 5
5 1
*/

#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cassert>
#include <algorithm>
#include <cstdlib>
#include <numeric>
#include <climits>
#include <fstream>

using namespace std;

#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define FORB(i, a, b) for (int i = a; i >= b; --i)
#define SZ(a) ((int) a.size())
#define ALL(a) begin(a), end(a)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define fi first
#define se second

// start of code


struct Seg
{
	int l, r, i;
	bool operator< (const Seg &s) const
	{
		return (l == s.l ? r > s.r : l < s.l);
	}
};

const int MAXN = 200007;
int N, M;
int cover[MAXN], par[MAXN], newIdx[MAXN], cnt, tmp, ptr;
vector<Seg> segs, segs1;
bool color[MAXN];

void addCover(Seg s, int _N = N)
{
	assert(s.l <= _N);
	if (s.r <= _N) {
		++ cover[s.l];
		-- cover[s.r + 1];
	} else {
		++ cover[s.l];
		-- cover[_N + 1];
		++ cover[1];
		-- cover[s.r - _N + 1];
	}
}

signed main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	// read
	cin >> N >> M;
	segs.resize(M);
	for (int i = 0; i < M; ++i) {
		cin >> segs[i].l >> segs[i].r;
		if (segs[i].l > segs[i].r) segs[i].r += N;
		segs[i].i = i;
		par[i] = -1;
	}

	// re-organize
	ptr = 0;
	for (int i = 1; i < M; ++i) {
		if (segs[i].r - segs[i].l > segs[ptr].r - segs[ptr].l) {
			ptr = i;
		}
	}

	int shiftBack = segs[ptr].l - 1;
	for (int i = 0; i < M; ++i) {
		segs[i].l -= shiftBack, segs[i].r -= shiftBack;
		if (segs[i].l <= 0) segs[i].l += N, segs[i].r += N;
	}

	// sort
	sort(segs.begin(), segs.end());

	// cout << "-1-" << endl;
	// for (Seg &s : segs) cout << s.l << ' ' << s.r << ": " << s.i << endl;
	// cout << "--" << endl;

	// remove interiors
	for (int i = 1; i <= N; ++i) cover[i] = 0;
	int ptr = 0; segs1.push_back(segs[0]);
	for (int i = 1; i < M; ++i) {
		if (segs[i].r <= segs[ptr].r) {
			par[segs[i].i] = segs[ptr].i;
			addCover(segs[i]);
		} else {
			ptr = i;
			segs1.push_back(segs[i]);
		}
	}
	segs1.swap(segs); segs1.clear();

	// calculate
	for (int i = 1; i <= N; ++i) {
		cover[i] += cover[i - 1];

		newIdx[i] = newIdx[i - 1];
		if (!cover[i]) ++newIdx[i];
	}
	int N2 = newIdx[N];
	for (int i = 1; i <= N; ++i) {
		newIdx[i + N] = newIdx[i] + N2;
	}

	// cout << "-2-" << endl;
	// for (Seg &s : segs) cout << s.l << ' ' << s.r << ": " << s.i << endl;
	// cout << "--" << endl;

	// for (int i = 1; i <= N; ++i) cout << cover[i]; cout << endl;

	for (Seg &s : segs) {
		s.l = newIdx[s.l - 1] + 1;
		s.r = newIdx[s.r];
		if (s.l > N2) s.l -= N2, s.r -= N2;
		if (s.l <= s.r) segs1.push_back(s);
	}

	// cout << "-3-" << endl;
	// for (Seg &s : segs1) cout << s.l << ' ' << s.r << ": " << s.i << endl;
	// cout << "--" << endl;

	for (int i = 1; i <= N; ++i) cover[i] = 0;
	for (Seg &s : segs1) addCover(s, N2);
	for (int i = 1; i <= N2; ++i) cover[i] += cover[i - 1];

	// check
	for (int i = 1; i <= N2; ++i) {
		if (cover[i] <= 1) return cout << "impossible\n", 0;
	}

	if (segs1.size() & 1) {
		if (segs1.size() == 1) return cout << "impossible\n", 0;

		bool flag = 0;
		for (int i = 0; i < (int) segs1.size() && !flag; ++i) {
			Seg sl = segs1[i - 2 < 0 ? i - 2 + segs1.size() : i - 2];
			Seg sm1 = segs1[i - 1 < 0 ? i - 1 + segs1.size() : i - 1];
			Seg sm2 = segs1[i];
			Seg sr = segs1[i + 1 >= (int) segs1.size() ? i + 1 - segs1.size() : i + 1];

			if (sm1.l < sl.l) sm1.l += N2, sm1.r += N2;
			if (sm2.l < sm1.l) sm2.l += N2, sm2.r += N2;
			if (sr.l < sm2.l) sr.l += N2, sr.r += N2;

			if (sl.r + 1 >= sr.l) {
				rotate(segs1.begin(), segs1.begin() + i, segs1.end());
				flag = 1;

				// cout << "-4-" << ' ' << i << endl;
				// for (Seg &s : segs1) cout << s.l << ' ' << s.r << ": " << s.i << endl;
				// cout << "--" << endl;
			}
		}

		if (!flag) return cout << "impossible\n", 0;
	}

	for (int i = 0; i < (int) segs1.size(); ++i) {
		color[segs1[i].i] = i & 1;
	}

	for (int i = 0; i < M; ++i) {
		if (par[i] >= 0) {
			color[i] = !color[par[i]];
		}
		cout << color[i];
	}
	cout << endl;

	return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26