Submission #544739

#	Time	Username	Problem	Language	Result	Execution time	Memory
544739		rainboy	Alternating Current (BOI18_alternating)	C11	100 / 100	46 ms	4908 KiB

alternating

#include <stdio.h>
#include <string.h>

#define N	100000
#define M	100000

int max(int a, int b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int ll[M], rr[M];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (ll[hh[j]] == ll[h])
				j++;
			else if (ll[hh[j]] < ll[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

int main() {
	static int kk[N * 2 + 1], hh[M], hh_[N * 2], ii[M], qu[M];
	static char ans[M + 1];
	int n, m, h, h_, i, cnt, cnt_, tmp;

	scanf("%d%d", &n, &m);
	h_ = 0;
	for (h = 0; h < m; h++) {
		scanf("%d%d", &ll[h], &rr[h]), ll[h]--, rr[h]--;
		if (h_ == -1 || (rr[h_] - ll[h_] + n) % n < (rr[h] - ll[h] + n) % n)
			h_ = h;
	}
	for (h = 0; h < m; h++)
		if (h != h_)
			ll[h] = (ll[h] - ll[h_] + n) % n, rr[h] = (rr[h] - ll[h_] + n) % n;
	rr[h_] = (rr[h_] - ll[h_] + n) % n, ll[h_] = 0;
	for (h = 0; h < m; h++) {
		if (rr[h] < ll[h])
			rr[h] += n;
		kk[ll[h]]++, kk[rr[h] + 1]--;
	}
	for (i = 1; i < n * 2; i++)
		kk[i] += kk[i - 1];
	for (i = 0; i < n; i++) {
		if (kk[i] + kk[n + i] < 2) {
			printf("impossible\n");
			return 0;
		}
		kk[i] = kk[n + i] = kk[i] + kk[n + i] == 2;
	}
	for (i = 1; i < n * 2; i++)
		kk[i] += kk[i - 1];
	for (h = 1; h < m; h++)
		hh[h] = h;
	hh[0] = h_, hh[h_] = 0;
	sort(hh, 1, m);
	memset(hh_, -1, n * 2 * sizeof *hh_);
	ii[0] = -1, hh_[rr[h_]] = h_;
	for (h = 1, i = 0; h < m; h++) {
		h_ = hh[h];
		while (i < n + n && (i + 1 < ll[h_] || hh_[i] == -1))
			i++;
		if (i < rr[h_] && kk[i] - (ll[h_] == 0 ? 0 : kk[ll[h_] - 1]) == 0)
			ii[h_] = i, hh_[rr[h_]] = h_;
		else
			ii[h_] = -1;
	}
	for (i = -1; i < n - 1; i++) {
		if (hh_[n + i] != -1)
			break;
		if (i <= rr[0] && kk[n + 1 + i] - kk[n + i] > 0) {
			i = n - 1;
			break;
		}
	}
	if (i == n - 1) {
		printf("impossible\n");
		return 0;
	}
	h = hh_[n + i];
	cnt = 0;
	while (h != hh[0])
		qu[cnt++] = h, h = hh_[ii[h]];
	qu[cnt++] = h;
	for (h = 0, h_ = cnt - 1; h < h_; h++, h_--)
		tmp = qu[h], qu[h] = qu[h_], qu[h_] = tmp;
	cnt_ = 0;
	for (h = 0; h < cnt; h++) {
		while (cnt_ > 1 && ll[qu[h]] < rr[qu[cnt_ - 2]] + 1)
			cnt_--;
		qu[cnt_++] = qu[h];
	}
	cnt = cnt_;
	h = 0;
	while (h + 1 < cnt && ll[qu[h + 1]] < rr[qu[cnt - 1]] - n + 1)
		h++;
	memset(ans, '0', m * sizeof *ans);
	while (h < cnt)
		ans[qu[h++]] = '1';
	printf("%s\n", ans);
	return 0;
}

Compilation message (stderr)

alternating.c: In function 'main':
alternating.c:41:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
alternating.c:44:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d%d", &ll[h], &rr[h]), ll[h]--, rr[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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