Submission #1067227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067227		sleepntsheep	Alternating Current (BOI18_alternating)	C++17	0 / 100	57 ms	18448 KiB

alternating

#include <stdio.h>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>

using namespace std;

template <typename T>
using ve = vector<T>;

template <typename T, int sz>
using ar = array<T, sz>;

int n, m;
char ans[1<<18];

int main() {
	scanf("%d%d", &n, &m);
	ve<int> col(m);
	ve<set<int> > g(m);
	ve<ar<int, 2>> a(m);
	ve<ve<int>> at(n+1);

	int j = 0;
	for (auto &[x, y] : a) {
		scanf("%d%d", &x, &y), --x, --y;
		if (x <= y)
			at[x].push_back(j), at[y + 1].push_back(j);
		else at[0].push_back(j), at[y + 1].push_back(j),
			at[x].push_back(j), at[n].push_back(j);
		++j;
	}


	set<int> walk;
	for (int i = 0; i < n; ++i) {
		for (auto j : at[i]) 
			if (0 == walk.count(j)) walk.insert(j);
			else walk.erase(j);
		if (walk.size() == 2) {
			g[*walk.begin()].insert(*++walk.begin());
			g[*++walk.begin()].insert(*walk.begin());
		}
		if (walk.size() < 2) exit(0 * puts("impossible"));
	}


	auto bicolor = [&](int u) {
		queue<int> q;
		q.emplace(u); col[u] = 1;
		while (q.size()) {
			int x = q.front();
			q.pop();
			for (auto v : g[x]) {
				if (col[v] == col[x])
					exit(0 * puts("impossible"));
				if (not col[v]) {
					col[v] = col[x] == 1 ? 2 : 1;
					q.push(x);
				}
			}
		}
	};

	for (int i = 0; i < m; ++i) if (g[i].size() and col[i] == 0) bicolor(i);


	walk.clear();
	ar<int, 3> cnt {};
	for (int i = 0; i < n; ++i) {
		for (auto j : at[i]) 
			if (0 == walk.count(j)) walk.insert(j), ++cnt[col[j]];
			else walk.erase(j), --cnt[col[j]];
		if (walk.size() >= 3) {
			int x[3] = {*walk.begin(), *++walk.begin(), *++++walk.begin()};
			if (cnt[1] and cnt[2]) continue;
			if (not cnt[1] and not cnt[2]) {
				col[x[0]] = 1;
				col[x[1]] = 2;
				++cnt[1], ++cnt[2];
			} else if (not cnt[1]) {
				for (int j : {0, 1, 2}) if (col[x[j]] == 0)  {
					col[x[j]] = 1;
					++cnt[1];
					break;
				}
			} else {
				for (int j : {0, 1, 2}) if (col[x[j]] == 0)  {
					col[x[j]] = 2;
					++cnt[2];
					break;
				}

			}
		}

		if (not cnt[1] or not cnt[2])
			exit(0 * puts("impossible"));
	}

	for (int i = 0; i < m; ++i) putchar(col[i] == 1 ? '1' : '0');
	return 0;
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
alternating.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%d%d", &x, &y), --x, --y;
      |   ~~~~~^~~~~~~~~~~~~~~~

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