#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <cassert> typedef struct { union { struct { int a, b, c; }; int x[3]; }; } abc_t; typedef struct { abc_t abc; int k, c; } stos_t; abc_t r; stos_t s[100001]; int w[100001]; #ifdef DEBUG #define DBG(x) (x) #else #define DBG(x) #endif int main(void) { int i; scanf("%d%d%d%d%d%d", &r.a, &r.b, &r.c, &s[0].abc.a, &s[0].abc.b, &s[0].abc.c); for (i = 0; i <= r.c; i++) w[i] = INT_MAX; for (i = 0; i < 3; i++) w[s[0].abc.x[i]] = 0; i = 0; while (i >= 0) { if (s[i].k < 6) { int d = s[i].k % 3; int b = (d + 1 + (s[i].k / 3)) % 3; int delta = s[i].abc.x[d]; int delta1 = r.x[b] - s[i].abc.x[b]; if (delta > delta1) delta = delta1; s[i].k++; if (delta > 0) { int j; int relaxed = 0; i++; DBG(assert(i < sizeof(s) / sizeof(s[0]))); s[i].abc = s[i - 1].abc; s[i].abc.x[d] -= delta; s[i].abc.x[b] += delta; s[i].k = 0; s[i].c = s[i - 1].c; DBG(fprintf(stderr, "%d(%d)\t%c->%c (%d)\t[%d %d %d]->[%d %d %d]\n", i, s[i - 1].k, 'A' + d, 'A' + b, delta, s[i - 1].abc.a, s[i - 1].abc.b, s[i - 1].abc.c, s[i].abc.a, s[i].abc.b, s[i].abc.c)); for (j = 0; j < 3; j++) { int v = s[i].abc.x[j]; DBG(assert(v <= r.c)); if (w[v] < 0 || w[v] >= i) { w[v] = i; relaxed++; } } if (!relaxed) { DBG(putc('!', stderr)); s[i].c++; if (s[i].c > 6) { i--; DBG(putc('\n', stderr)); } } } } else { i--; } } for (i = 0; i < r.c; i++) printf("%d ", w[i] == INT_MAX ? -1 : w[i]); printf("%d\n", w[i] == INT_MAX ? -1 : w[i]); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <cassert> typedef struct { union { struct { int a, b, c; }; int x[3]; }; } abc_t; typedef struct { abc_t abc; int k, c; } stos_t; abc_t r; stos_t s[100001]; int w[100001]; #ifdef DEBUG #define DBG(x) (x) #else #define DBG(x) #endif int main(void) { int i; scanf("%d%d%d%d%d%d", &r.a, &r.b, &r.c, &s[0].abc.a, &s[0].abc.b, &s[0].abc.c); for (i = 0; i <= r.c; i++) w[i] = INT_MAX; for (i = 0; i < 3; i++) w[s[0].abc.x[i]] = 0; i = 0; while (i >= 0) { if (s[i].k < 6) { int d = s[i].k % 3; int b = (d + 1 + (s[i].k / 3)) % 3; int delta = s[i].abc.x[d]; int delta1 = r.x[b] - s[i].abc.x[b]; if (delta > delta1) delta = delta1; s[i].k++; if (delta > 0) { int j; int relaxed = 0; i++; DBG(assert(i < sizeof(s) / sizeof(s[0]))); s[i].abc = s[i - 1].abc; s[i].abc.x[d] -= delta; s[i].abc.x[b] += delta; s[i].k = 0; s[i].c = s[i - 1].c; DBG(fprintf(stderr, "%d(%d)\t%c->%c (%d)\t[%d %d %d]->[%d %d %d]\n", i, s[i - 1].k, 'A' + d, 'A' + b, delta, s[i - 1].abc.a, s[i - 1].abc.b, s[i - 1].abc.c, s[i].abc.a, s[i].abc.b, s[i].abc.c)); for (j = 0; j < 3; j++) { int v = s[i].abc.x[j]; DBG(assert(v <= r.c)); if (w[v] < 0 || w[v] >= i) { w[v] = i; relaxed++; } } if (!relaxed) { DBG(putc('!', stderr)); s[i].c++; if (s[i].c > 6) { i--; DBG(putc('\n', stderr)); } } } } else { i--; } } for (i = 0; i < r.c; i++) printf("%d ", w[i] == INT_MAX ? -1 : w[i]); printf("%d\n", w[i] == INT_MAX ? -1 : w[i]); return 0; } |