oj.uz

Submission #916404

# Submission time Handle Problem Language Result Execution time Memory
916404 2024-01-25T19:45:25 Z rainboy Permutation Recovery (info1cup17_permutation) C++
100 / 100
 3655 ms 232628 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	70000
#define B	1000000000000000000
#define L	18

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

unsigned int Z = 12345;

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

void print(long long *aa, int n) {
	int i;

	if (n == 0) {
		printf("0\n");
		return;
	}
	i = n - 1;
	while (i > 0 && aa[i] == 0)
		i--;
	printf("%lld", aa[i]);
	while (i--)
		printf("%018lld", aa[i]);
}

long long *add(long long *aa, int n, long long *bb, int m, int *n1) {
	long long *cc;
	int n_, i;

	if (n == 0 && m == 0) {
		*n1 = 0;
		return NULL;
	}
	n_ = max(n, m);
	cc = (long long *) malloc(n_ * sizeof *cc);
	for (i = 0; i < n_; i++)
		cc[i] = (i < n ? aa[i] : 0) + (i < m ? bb[i] : 0);
	for (i = 0; i + 1 < n_; i++)
		if (cc[i] >= B)
			cc[i] -= B, cc[i + 1]++;
	if (cc[n_ - 1] >= B) {
		cc = (long long *) realloc(cc, n_ * 2 * sizeof *cc);
		memset(cc + n_, 0, n_ * sizeof *cc);
		cc[n_ - 1] -= B, cc[n_]++;
		n_ *= 2;
	}
	*n1 = n_;
	return cc;
}

void subtract(long long *aa, int n, long long *bb, int m, int *n1) {
	int n_, i;

	for (i = 0; i < m; i++)
		aa[i] -= bb[i];
	for (i = 0; i < n; i++)
		if (aa[i] < 0)
			aa[i] += B, aa[i + 1]--;
	n_ = n;
	while (n_ >= 2 && aa[n_ - 1] == 0)
		n_--;
	while ((n_ & n_ - 1) != 0)
		n_++;
	if (n_ != n)
		aa = (long long *) realloc(aa, n_ * sizeof *aa);
	*n1 = n_;
}

int compare(long long *aa, int n, long long *bb, int m) {
	int h;

	if (n != m)
		return n - m;
	for (h = n - 1; h >= 0; h--)
		if (aa[h] != bb[h])
			return aa[h] < bb[h] ? -1 : 1;
	return 0;
}

long long *aa[N]; int nn[N];
int zz[N + 1], ii[N + 1], ll[N + 1], rr[N + 1]; long long *ss[N + 1]; int nn_[N + 1];

int node(int i) {
	static int _ = 1;

	zz[_] = rand_();
	ii[_] = i;
	ss[_] = (long long *) malloc(nn[i] * sizeof *ss[_]);
	memcpy(ss[_], aa[i], (nn_[_] = nn[i]) * sizeof *aa[i]);
	return _++;
}

void pul(int u) {
	int l, r;
	long long *tmp;
	int n;

	l = ll[u], r = rr[u];
	if (ss[u])
		free(ss[u]);
	tmp = add(ss[l], nn_[l], ss[r], nn_[r], &n);
	ss[u] = add(tmp, n, aa[ii[u]], nn[ii[u]], &nn_[u]);
	if (tmp)
		free(tmp);
}

long long *aa_; int n_, u_, l_, r_;

void split(int u) {
	if (u == 0) {
		l_ = 0, r_ = 0;
		return;
	}
	if (compare(aa_, n_, ss[ll[u]], nn_[ll[u]]) <= 0) {
		split(ll[u]);
		ll[u] = r_, r_ = u;
	} else {
		subtract(aa_, n_, ss[ll[u]], nn_[ll[u]], &n_);
		if (compare(aa_, n_, aa[ii[u]], nn[ii[u]]) <= 0) {
			l_ = ll[u], r_ = u;
			ll[u] = 0;
		} else {
			subtract(aa_, n_, aa[ii[u]], nn[ii[u]], &n_);
			split(rr[u]);
			rr[u] = l_, l_ = u;
		}
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v), pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]), pul(v);
		return v;
	}
}

int pp[N], p;

void dfs(int u) {
	if (u == 0)
		return;
	dfs(ll[u]), pp[ii[u]] = p++, dfs(rr[u]);
}

int main() {
	int n, g, gl, gr, h, i;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		static char cc[N + 1];
		int l;

		scanf("%s", cc), l = strlen(cc);
		nn[i] = (l + L - 1) / L;
		while ((nn[i] & nn[i] - 1) != 0)
			nn[i]++;
		aa[i] = (long long *) malloc(nn[i] * sizeof *aa[i]);
		for (h = 0; h < nn[i]; h++) {
			gl = max(l - (h + 1) * L, 0), gr = max(l - h * L, 0);
			aa[i][h] = 0;
			for (g = gl; g < gr; g++)
				aa[i][h] = aa[i][h] * 10 + (cc[g] - '0');
		}
	}
	for (i = n - 1; i > 0; i--)
		subtract(aa[i], nn[i], aa[i - 1], nn[i - 1], &nn[i]);
	for (i = 0; i < n; i++) {
		aa_ = (long long *) malloc(nn[i] * sizeof *aa_);
		memcpy(aa_, aa[i], (n_ = nn[i]) * sizeof *aa);
		split(u_);
		u_ = merge(merge(l_, node(i)), r_);
	}
	dfs(u_);
	for (i = 0; i < n; i++)
		printf("%d ", pp[i] + 1);
	printf("\n");
	return 0;
}

Compilation message

permutation.cpp: In function 'void subtract(long long int*, int, long long int*, int, int*)':
permutation.cpp:68:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   68 |  while ((n_ & n_ - 1) != 0)
      |               ~~~^~~
permutation.cpp: In function 'int main()':
permutation.cpp:169:25: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  169 |   while ((nn[i] & nn[i] - 1) != 0)
      |                   ~~~~~~^~~
permutation.cpp:162:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
permutation.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |   scanf("%s", cc), l = strlen(cc);
      |   ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 235 ms 14336 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 235 ms 14336 KB Output is correct
6 Correct 566 ms 30364 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 235 ms 14336 KB Output is correct
6 Correct 566 ms 30364 KB Output is correct
7 Correct 779 ms 41408 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 235 ms 14336 KB Output is correct
6 Correct 566 ms 30364 KB Output is correct
7 Correct 779 ms 41408 KB Output is correct
8 Correct 2528 ms 178612 KB Output is correct
9 Correct 2577 ms 156772 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 235 ms 14336 KB Output is correct
6 Correct 566 ms 30364 KB Output is correct
7 Correct 779 ms 41408 KB Output is correct
8 Correct 2528 ms 178612 KB Output is correct
9 Correct 2577 ms 156772 KB Output is correct
10 Correct 3655 ms 232628 KB Output is correct