Submission #527965

#	Time	Username	Problem	Language	Result	Execution time	Memory
527965		LucaDantas	Alternating Current (BOI18_alternating)	C++17	19 / 100	44 ms	5568 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();
		if((l >= ini_mx) == (o.l >= ini_mx)) return l < o.l; // retorno o que tem o menor l já que eles são da mesma metade
		return l > o.l; // já que eles são de metades diferentes eu retorno o que tiver na metade maior
	}
} 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]--;
		}
		
		if(wr[i].sz() > mx) {
			mx = wr[i].sz();
			ini_mx = wr[i].l;
		}
	}

	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);

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

	vector<Wire> brabos;

	memset(pai, -1, sizeof pai);
	for(int i = 0; i < m; i++) {
		auto [l, r, id] = wr[i];
		if(r < l) r += n;
		if(make_pair(virou, fim) < make_pair(min(l, r) < ini_mx, r)) {
			brabos.push_back(wr[i]);
			aberto = id;
			fim = r;
			virou |= min(l, r) < ini_mx;
		} else pai[id] = aberto;
	}

	/* 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 = 1;
			ans[ brabos[i].id ] = opa;

			for(int j = nxt(i); j != i; j = nxt(j)) {
				ans[ brabos[j].id ] = opa;
				opa ^= 1;
			}

			for(int i = 0; i < m; i++)
				if(pai[i] != -1) ans[i] = 1^ans[pai[i]];

			print();
		}
	}

	puts("impossible");
}

Compilation message (stderr)

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

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