oj.uz

Submission #503401

# Submission time Handle Problem Language Result Execution time Memory
503401 2022-01-07T20:13:52 Z rainboy Akcija (COCI21_akcija) C
60 / 110
 35 ms 1100 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	2000
#define K	2000
#define S	2000000000002LL

unsigned int X = 12345;

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

int ww[N], *ei[N], eo[N], n;

void append(int t, int i) {
	int o = eo[t]++;

	if (o >= 2 && (o & o - 1) == 0)
		ei[t] = (int *) realloc(ei[t], o * 2 * sizeof *ei[t]);
	ei[t][o] = i;
}

int cc[K], k_, k; long long ss[K];

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 (cc[hh[j]] == cc[h] && ss[hh[j]] == ss[h])
				j++;
			else if (cc[hh[j]] > cc[h] || cc[hh[j]] == cc[h] && ss[hh[j]] < ss[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 iq[1 + N], pq[N], cnt;

int lt(int i, int j) { return ww[i] < ww[j]; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add(int i) {
	pq[i] = ++cnt, pq_up(i);
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];

	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

int c1; long long s1;

void greedy(char *used) {
	int i, t, o;

	memset(used, 0, n * sizeof *used);
	cnt = 0, c1 = s1 = 0;
	for (t = n - 1; t >= 0; t--) {
		for (o = eo[t]; o--; ) {
			i = ei[t][o];
			pq_add(i);
		}
		if (cnt) {
			i = pq_remove_first();
			c1++, s1 += ww[i], used[i] = 1;
		}
	}
}

void get_subs(char *used, char *banned, int *sub) {
	static int kk[N];
	int i, i_, c, s, t, o;

	memset(kk, 0, n * sizeof *kk);
	c = 0;
	for (t = 0; t < n; t++)
		for (o = eo[t]; o--; ) {
			i = ei[t][o];
			if (used[i])
				kk[t]++, kk[c++]--;
		}
	for (t = n - 2; t >= 0; t--)
		kk[t] += kk[t + 1];
	for (s = n - 1, t = n - 1, i_ = -1; s >= 0; s--) {
		while (t >= s || kk[t + 1] > 0) {
			for (o = eo[t]; o--; ) {
				i = ei[t][o];
				if (!banned[i] && !used[i] && (i_ == -1 || ww[i_] > ww[i]))
					i_ = i;
			}
			t--;
		}
		for (o = eo[s]; o--; ) {
			i = ei[s][o];
			if (used[i])
				sub[i] = i_;
		}
	}
}

char used[N + 1][N], banned[N + 1][N]; int sub[N + 1][N], n_;

int branch(int n, int h, int c, long long s, int c_, long long s_) {
	int i;

	if (c < c_ || c == c_ && s > s_)
		return 0;
	get_subs(used[h], banned[h], sub[h]);
	cc[k_] = c, ss[k_] = s, k_++;
	if (k_ == k) {
		n_--;
		return 1;
	}
	memcpy(used[h + 1], used[h], n * sizeof *used[h]);
	memcpy(banned[h + 1], banned[h], n * sizeof *banned[h]);
	for (i = 0; i < n; i++)
		if (used[h + 1][i] == 1) {
			int j, c1;
			long long s1;

			used[h + 1][i] = 0, banned[h + 1][i] = 1;
			j = sub[h][i];
			if (j == -1)
				c1 = c - 1, s1 = s - ww[i];
			else {
				c1 = c, s1 = s - ww[i] + ww[j];
				used[h + 1][j] = 1;
			}
			if ((c1 >= c_ || c1 == c_ && s1 <= s_) && branch(n, h + 1, c1, s1, c_, s_))
				return 1;
			used[h + 1][i] = -1, banned[h + 1][i] = 0;
			if (j != -1)
				used[h + 1][j] = 0;
		}
	return 0;
}

int main() {
	static int hh[K];
	int h, i, t, c;
	long long lower, upper, cs, s;

	scanf("%d%d", &n, &k);
	for (t = 0; t < n; t++)
		ei[t] = (int *) malloc(2 * sizeof *ei[t]);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &ww[i], &t), t--;
		append(t, i);
	}
	greedy(used[0]);
	lower = -1, upper = (n + 2) * S;
	while (upper - lower > 1) {
		cs = (lower + upper) / 2, c = n - cs / S, s = cs % S;
		k_ = 0;
		if ((c1 > c || c1 == c && s1 < s) && branch(n, 0, c1, s1, c, s))
			upper = cs;
		else
			lower = cs;
	}
	if (lower >= 0) {
		cs = lower, c = n - cs / S, s = cs % S;
		if (c1 > c || c1 == c && s1 < s)
			k_ = 0, branch(n, 0, c1, s1, c, s);
	}
	cs = upper, c = n - cs / S, s = cs % S;
	while (k_ < k)
		cc[k_] = c, ss[k_] = s, k_++;
	for (h = 0; h < k; h++)
		hh[h] = h;
	sort(hh, 0, k);
	for (h = 0; h < k; h++)
		printf("%d %lld\n", cc[hh[h]], ss[hh[h]]);
	return 0;
}

Compilation message

Main.c: In function 'append':
Main.c:20:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   20 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'sort':
Main.c:34:53: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   34 |    else if (cc[hh[j]] > cc[h] || cc[hh[j]] == cc[h] && ss[hh[j]] < ss[h]) {
      |                                  ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.c: In function 'branch':
Main.c:138:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  138 |  if (c < c_ || c == c_ && s > s_)
      |                ~~~~~~~~^~~~~~~~~
Main.c:161:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  161 |    if ((c1 >= c_ || c1 == c_ && s1 <= s_) && branch(n, h + 1, c1, s1, c_, s_))
      |                     ~~~~~~~~~^~~~~~~~~~~
Main.c: In function 'main':
Main.c:187:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  187 |   if ((c1 > c || c1 == c && s1 < s) && branch(n, 0, c1, s1, c, s))
      |                  ~~~~~~~~^~~~~~~~~
Main.c:194:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  194 |   if (c1 > c || c1 == c && s1 < s)
      |                 ~~~~~~~~^~~~~~~~~
Main.c:175:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:179:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |   scanf("%d%d", &ww[i], &t), t--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Incorrect 3 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Incorrect 3 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 452 KB Output is correct
2 Correct 35 ms 420 KB Output is correct
3 Correct 31 ms 416 KB Output is correct
4 Correct 26 ms 424 KB Output is correct
5 Correct 27 ms 428 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 27 ms 468 KB Output is correct
8 Correct 23 ms 468 KB Output is correct
9 Correct 31 ms 480 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 35 ms 412 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 716 KB Output is correct
2 Correct 6 ms 716 KB Output is correct
3 Correct 8 ms 724 KB Output is correct
4 Correct 6 ms 716 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 5 ms 972 KB Output is correct
7 Correct 5 ms 1100 KB Output is correct
8 Correct 4 ms 972 KB Output is correct
9 Correct 5 ms 972 KB Output is correct
10 Correct 5 ms 716 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 3 ms 460 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Incorrect 3 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -