結果
問題 | No.332 数列をプレゼントに |
ユーザー |
![]() |
提出日時 | 2019-07-08 09:41:10 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 1,894 bytes |
コンパイル時間 | 1,091 ms |
コンパイル使用メモリ | 31,104 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-07 21:41:55 |
合計ジャッジ時間 | 2,330 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
コンパイルメッセージ
main.c: In function 'in': main.c:10:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration] 10 | #define gc() getchar_unlocked() | ^~~~~~~~~~~~~~~~ main.c:18:27: note: in expansion of macro 'gc' 18 | ll n = 0; int c = gc(); | ^~ main.c: In function 'outs': main.c:11:15: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration] 11 | #define pc(c) putchar_unlocked(c) | ^~~~~~~~~~~~~~~~ main.c:23:33: note: in expansion of macro 'pc' 23 | void outs(char *s) { while (*s) pc(*s++); pc('\n'); } | ^~
ソースコード
// yukicoder: No.332 数列をプレゼントに// 2019.7.8 bal4u#include <stdio.h>#include <stdlib.h>typedef long long ll;#if 1#define gc() getchar_unlocked()#define pc(c) putchar_unlocked(c)#else#define gc() getchar()#define pc(c) putchar(c)#endifll in() { // 非負整数の入力ll n = 0; int c = gc();do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');return n;}void outs(char *s) { while (*s) pc(*s++); pc('\n'); }void outc(int f, char c) { while (f--) pc(c); pc('\n'); }#define LIM 100000typedef struct { int v, id; } T;T a[105], b[105]; int fa, fb; int N; ll X;char f[105];int dp[80*LIM];int cmp(const void *a, const void *b) { return ((T *)a)->v - ((T *)b)->v; }void final(int p, int q) {int i;// printf("final: p=%d, q=%x\n", p, q); fflush(stdout);while (p) {// printf("p=%d, prev=%d, id=%d\n", p, dp[p] >> 7, (dp[p] & 127)-1);f[(dp[p] & 127)-1] = 1;p = dp[p] >> 7;}for (i = 0; q; i++) {if (q & 1) {f[b[i].id] = 1;// printf("q=%d, x=%d, id=%d\n", i, b[i].id);}q >>= 1;}for (i = 0; i < N; i++) pc(f[i]? 'o': 'x');pc('\n');exit(0);}int main(){int i, j, x, ma;ll s;N = (int)in(), X = in(), s = 0, fa = 1, fb = 0;for (i = 0; i < N; i++) {x = (int)in(), s += x;if (x <= LIM) a[++fa].id = i, a[fa].v = x;else b[fb].id = i, b[fb++].v = x;}if (s == X) { outc(N, 'o'); return 0; }qsort(a+2, fa-1, sizeof(T), cmp);// printf("fa=%d, fb=%d\n", fa, fb);dp[0] = 1, ma = 0;for (i = 2; i <= fa; i++) {for (j = ma; j >= 0; j--) {if (dp[j] && !dp[j+a[i].v]) dp[j+a[i].v] = (j << 7) | (a[i].id+1);}ma += a[i].v;}// printf("ma=%d\n", ma);if (X <= ma && dp[X]) final(X, 0);i = 1 << fb; while (--i) {s = 0, x = i;for (j = 0; x; j++) {if (x & 1) s += b[j].v;x >>= 1;}if (s <= X && X-s <= ma && dp[X-s]) final(X-s, i);}outs("No");return 0;}