Submission #528612

#	Time	Username	Problem	Language	Result	Execution time	Memory
528612		LucaDantas	Alternating Current (BOI18_alternating)	C++17	100 / 100	40 ms	5632 KiB

alternating

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 3e5+10;

int pref[maxn];
int mx = 0, ini_mx = 0, n, m;

struct Wire {
	int l, r, id;
	int sz() const { return r >= l ? r - l + 1 : r + (n - l + 1); }
	bool operator<(const Wire& o) const {
		if(l == o.l) return this->sz() > o.sz();
		return l < o.l;
	}
	bool inside(const Wire& o) const {
		int st = (l - o.l + n) % n;
		return st + this->sz() <= o.sz();
	}
} wr[maxn];

int pai[maxn];

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++) {
		scanf("%d %d", &wr[i].l, &wr[i].r); wr[i].id = i;
		if(wr[i].l <= wr[i].r) {
			pref[wr[i].l]++;
			pref[wr[i].r+1]--;
		} else {
			pref[wr[i].l]++;
			pref[1]++;
			pref[wr[i].r+1]--;
		}
	}

	for(int i = 1; i <= n; i++) {
		pref[i] += pref[i-1];
		pref[i+n] = pref[i];
		if(pref[i] < 2) return puts("impossible"), 0;
	}

	sort(wr, wr+m);

	int virou = 0;
	int fim = 0, aberto = -1;

	vector<Wire> brabos;

	memset(pai, -1, sizeof pai);
	Wire last = wr[0];
	for(int rep = 0; rep < 2; rep++) {
		for(int i = !rep; i < m; i++) {
			if(wr[i].inside(last) && wr[i].id != last.id) {
				if(rep) pai[wr[i].id] = last.id;
			} else {
				if(rep) brabos.push_back(wr[i]);
				last = wr[i];
			}
		}
	}

	/* puts("BRABOS: ");
	printf("Size: %ld\n", brabos.size());
	for(Wire x : brabos)
		printf("(%d %d %d) ", x.l, x.r, x.id);
	puts(""); */

	vector<int> ans(m);

	auto print = [&]() {
		for(int i = 0; i < m; i++)
			printf("%d", ans[i]);
		puts("");
		exit(0);
	};

	if(brabos[0].sz() == n) {
		ans[brabos[0].id] = 1;
		print();
	}

	if(brabos.size() % 2 == 0) {
		for(int i = 0; i < brabos.size(); i++)
			ans[brabos[i].id] = i&1;
		
		for(int i = 0; i < m; i++)
			if(pai[i] != -1) ans[i] = 1^ans[pai[i]];

		print();
	}

	sort(brabos.begin(), brabos.end(), [](const Wire& a, const Wire& b) { return a.l < b.l; });

	for(int i = 0; i < brabos.size(); i++) {
		auto nxt = [&](int x) { return (x+1) % brabos.size(); };
		auto eu = brabos[i], prox = brabos[nxt(i)];
		int l = prox.l, r = eu.r;
		
		if(r < l) r += n;

		bool tem = 1;
		for(int j = l; j <= r; j++)
			tem &= pref[j] >= 3;

		auto no_intersection = [](Wire a, Wire b) {
			if(a.r < a.l) a.r += n;
			if(b.r < b.l) b.r += n;

			if(a.r < b.l) return 1;
			return 0;
		};
		if(tem || no_intersection(eu, prox)) {
			// printf("BOM %d | %d %d\n", i, l, r);

			bool opa = 0;
			ans[ brabos[i].id ] = opa;

			for(int j = nxt(i); j != i; j = nxt(j)) {
				// printf("to %d %d\n", j, opa);
				ans[ brabos[j].id ] = opa;
				opa ^= 1;
			}

			for(int i = 0; i < m; i++)
				if(pai[i] != -1) ans[i] = 1^ans[pai[i]];
				// else printf("sai corno %d\n", i);

			print();
		}
	}

	puts("impossible");
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for(int i = 0; i < brabos.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~
alternating.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(int i = 0; i < brabos.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
alternating.cpp:46:6: warning: unused variable 'virou' [-Wunused-variable]
   46 |  int virou = 0;
      |      ^~~~~
alternating.cpp:47:6: warning: unused variable 'fim' [-Wunused-variable]
   47 |  int fim = 0, aberto = -1;
      |      ^~~
alternating.cpp:47:15: warning: unused variable 'aberto' [-Wunused-variable]
   47 |  int fim = 0, aberto = -1;
      |               ^~~~~~
alternating.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
alternating.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%d %d", &wr[i].l, &wr[i].r); wr[i].id = i;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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