oj.uz

답안 #547194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
547194 2022-04-09T19:13:43 Z skittles1412 Alternating Current (BOI18_alternating) C++17
0 / 100
 3000 ms 8484 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

void solve() {
	int n, m;
	cin >> n >> m;
	array<int, 3> arr[m];
	for (int i = 0; i < m; i++) {
		cin >> arr[i][0] >> arr[i][1];
		arr[i][0]--;
		arr[i][1]--;
		arr[i][2] = i;
	}
	sort(arr, arr + m, [&](const auto& a, const auto& b) -> bool {
		if (a[0] != b[0]) {
			return a[0] < b[0];
		}
		return a[1] > b[1];
	});
	int par[m];
	pair<int, int> mx {-1, -1};
	for (int i = 0; i < m; i++) {
		auto [l, r, _] = arr[i];
		dbg(i, l, r);
		if (l > r) {
			r += n;
		}
		if (r <= mx.first) {
			par[i] = mx.second;
		} else {
			par[i] = i;
			mx = {r, i};
		}
	}
	for (int i = 0; i < m; i++) {
		int u = i;
		while (par[u] != u) {
			u = par[u];
		}
		par[i] = u;
	}
	vector<int> vals;
	int inds[m];
	for (int i = 0; i < m; i++) {
		if (par[i] == i) {
			inds[i] = sz(vals);
			vals.push_back(i);
		}
		dbg(i, par[i]);
	}
	auto covers_all = [&](const vector<pair<int, int>> &arr) -> bool {
		vector<int> e[n];
		for (auto& [l, r] : arr) {
			e[l].push_back(r);
		}
		int mx = -1;
		for (int i = 0; i < n; i++) {
			for (auto& a : e[i]) {
				mx = max(mx, a);
			}
			if (mx < i) {
				return false;
			}
		}
		return true;
	};
	auto check = [&](const vector<bool> &distr) -> void {
		vector<pair<int, int>> segs[2];
		auto add = [&](int i, int l, int r) -> void {
			if (l > r) {
				segs[i].emplace_back(l, n - 1);
				segs[i].emplace_back(0, r);
			} else {
				segs[i].emplace_back(l, r);
			}
		};
		bool ans[m];
		for (auto& a : inds) {
			a &= 1;
		}
		for (int i = 0; i < m; i++) {
			auto &[l, r, ci] = arr[i];
			if (par[i] == i) {
				ans[ci] = distr[inds[i]];
			} else {
				ans[ci] = !distr[inds[par[i]]];
			}
			dbg(i, ans[ci]);
			add(ans[ci], l, r);
		}
		if (covers_all(segs[0]) && covers_all(segs[1])) {
			for (auto& a : ans) {
				cout << a;
			}
			cout << endl;
			exit(0);
		}
	};
	int k = sz(vals);
	if (k % 2 == 0 || k == 1) {
		vector<bool> distr(k);
		for (int i = 0; i < k; i++) {
			distr[i] = i & 1;
		}
		check(distr);
		cout << "impossible" << endl;
		return;
	}
	for (int i = 0; i < k; i++) {
		vector<bool> distr(k);
		int j = i;
		bool cur = false;
		while (true) {
			distr[j] = cur;
			cur ^= true;
			j = j + 1 == k ? 0 : j + 1;
			if (j == i) {
				break;
			}
		}
		check(distr);
	}
	cout << "impossible" << endl;
	return;
	{
		vector<pair<int, int>> cur;
		for (auto& [l, r, _] : arr) {
			if (l > r) {
				cur.emplace_back(l, n - 1);
				cur.emplace_back(0, r);
			} else {
				cur.emplace_back(l, r);
			}
		}
		if (!covers_all(cur)) {
			cout << "impossible" << endl;
			return;
		}
	}
	bool can[k];
	vector<pair<int, int>> child[k];
	for (int i = 0; i < m; i++) {
		auto &[l, r, _] = arr[i];
		if (par[i] != i) {
			child[par[i]].emplace_back(l, r);
		}
	}
	auto norm = [&](vector<pair<int, int>> &arr) -> void {
		for (auto& [l, r] : arr) {
			if (l > r) {
				r += n;
			}
		}
	};
	for (int i = 0; i < k; i++) {
		auto cl = child[i ? i - 1 : k - 1];
		auto cr = child[i + 1 == k ? 0 : i + 1];
		norm(cl);
		norm(cr);
		int mxl = -2, mnr = 1e9;
		for (auto& [l, r] : cl) {
			mxl = max(mxl, r);
		}
		for (auto& [l, r] : cr) {
			mnr = min(mnr, l);
		}
		can[i] = mxl + 1 == mnr;
	}
	int cnt = 0;
	for (auto& a : can) {
		cnt += a;
	}
	for (int i = 0; i < k; i++) {
		int j = i + 1 == k ? 0 : i + 1;
		int ccnt = cnt - can[i] - can[j];
		if (ccnt != k - 2) {
			continue;
		}
		
	}
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 7216 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 13 ms 6220 KB Output is correct
4 Correct 20 ms 6228 KB Output is correct
5 Correct 40 ms 8144 KB Output is correct
6 Execution timed out 3057 ms 8484 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -