Submission #871019

#	Time	Username	Problem	Language	Result	Execution time	Memory
871019		rainboy	Devil's Share (RMI19_devil)	C11	100 / 100	56 ms	9820 KiB

devil

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

#define N	1000000
#define D	10

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		static int kk[N + D], kk_[D], ll[N + D], rr[N + D], qu[N];
		static char cc[N + 1];
		int n, m, m_, cnt, k, k_, d;

		scanf("%d", &k);
		n = 0;
		for (d = 1; d < D; d++) {
			scanf("%d", &kk[d]);
			n += kk[d];
		}
		memset(kk_, 0, D * sizeof *kk_);
		for (d = D - 1, k_ = k - 1; d >= 0; d--)
			if (k_ > kk[d])
				kk_[d] = kk[d], k_ -= kk[d], kk[d] = 0;
			else {
				kk_[d] = k_, kk[d] -= k_;
				break;
			}
		m = D;
		while (m >= 0 && kk[m - 1] == 0)
			m--;
		memset(ll, -1, m * sizeof *ll), memset(rr, -1, m * sizeof *rr);
		cnt = n - k, d = 0;
		while (1) {
			if (kk[m - 1] == cnt + 1) {
				cnt = 0;
				while (kk[m - 1]--)
					qu[cnt++] = m - 1;
				break;
			}
			cnt -= kk[m - 1];
			m_ = m;
			while (kk[m - 1] > 0) {
				while (d == m - 1 || kk[d] == 0)
					d++;
				ll[m_] = m - 1, rr[m_] = d;
				if (kk[m - 1] > kk[d])
					kk[m_] = kk[d], kk[m - 1] -= kk[d], kk[d] = 0;
				else
					kk[m_] = kk[m - 1], kk[d] -= kk[m - 1], kk[m - 1] = 0;
				m_++;
			}
			m = m_;
		}
		n = 0;
		while (cnt--) {
			d = qu[cnt];
			if (ll[d] == -1 && rr[d] == -1)
				cc[n++] = d + '0';
			else
				qu[cnt++] = rr[d], qu[cnt++] = ll[d];
		}
		for (d = 0; d < D; d++)
			while (kk_[d]--)
				cc[n++] = d + '0';
		cc[n] = 0;
		printf("%s\n", cc);
	}
	return 0;
}

Compilation message (stderr)

devil.c: In function 'main':
devil.c:10:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
devil.c:16:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%d", &k);
      |   ^~~~~~~~~~~~~~~
devil.c:19:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |    scanf("%d", &kk[d]);
      |    ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 29 / 29
• Subtask 4: 44 / 44