結果
問題 | No.868 ハイパー部分和問題 |
ユーザー |
|
提出日時 | 2019-08-16 00:47:30 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 962 ms / 7,000 ms |
コード長 | 8,571 bytes |
コンパイル時間 | 734 ms |
コンパイル使用メモリ | 35,072 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-23 06:52:47 |
合計ジャッジ時間 | 13,215 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#if 0cat <<EOF >mistaken-paste#endif// thx Ebi-chan!#pragma GCC diagnostic ignored "-Wincompatible-pointer-types"#define _USE_MATH_DEFINES#include <stdio.h>#include <stdint.h>#include <stdlib.h>#include <string.h>#include <stdbool.h>#include <math.h>#include <time.h>#define BIG 2000000007#define VERYBIG 20000000000000007LL#define MOD 1000000007#define FOD 998244353typedef uint64_t ull;typedef int64_t sll;#define N_MAX 1048576#ifdef __cplusplus#include <queue>#include <stack>#include <tuple>#include <set>#include <map>#include <string>#include <algorithm>#include <functional>#include <array>using std::queue;using std::priority_queue;using std::stack;using std::tuple;using std::set;using std::map;using std::vector;using std::greater;using std::pair;using std::string;using std::get;template <typename T, typename U>pair<T, U> operator+(pair<T, U> l, pair<T, U> r) {return pair<T, U>(l.first + r.first, l.second + r.second);}#endif#ifndef M_PI#define M_PI 3.14159265358979323846264338327950#endiftypedef struct {sll a;sll b;} hwll;typedef struct {sll a;sll b;sll c;} hwllc;typedef struct {hwll a;hwll b;} linell;typedef struct {double a;double b;} hwreal;sll n, m;sll h, w;sll k;sll q;sll va, vb, vc, vd, ve, vf;ull ua, ub, uc, ud, ue, uf;long double vra, vrb, vrc;double vda, vdb, vdc;char ch, dh;ull umin (ull x, ull y) {return (x < y) ? x : y;}ull umax (ull x, ull y) {return (x > y) ? x : y;}sll smin (sll x, sll y) {return (x < y) ? x : y;}sll smax (sll x, sll y) {return (x > y) ? x : y;}ull gcd (ull x, ull y) {if (y == 0) {return x;} else {return gcd(y, x % y);}}ull bitpow (ull a, ull x, ull modulo) {ull result = 1;while (x) {if (x & 1) {result *= a;result %= modulo;}x /= 2;a = (a * a) % modulo;}return result;}ull divide (ull a, ull b, ull modulo) {return (a * bitpow(b, modulo - 2, modulo)) % modulo;}ull udiff (ull a, ull b) {if (a >= b) {return a - b;} else {return b - a;}}sll sdiff (sll a, sll b) {if (a >= b) {return a - b;} else {return b - a;}}int bitcount (ull n) {int result = 0;while (n) {if (n & 1) result++;n /= 2;}return result;}#define BEGCMP(NAME) int32_t NAME (const void *left, const void *right)#define DEFLR(TYPE) TYPE l=*(TYPE*)left,r=*(TYPE*)right#define CMPRET(L, R) if((L)<(R))return-1;if((L)>(R))return+1// int32_t pullcomp (const void *left, const void *right) {// ull l = *(ull*)left;// ull r = *(ull*)right;// if (l < r) {// return -1;// }// if (l > r) {// return +1;// }// return 0;// }BEGCMP(pullcomp){DEFLR(ull);CMPRET(l, r);return 0;}BEGCMP(prevcomp){DEFLR(sll);CMPRET(r, l);return 0;}BEGCMP(psllcomp){DEFLR(sll);CMPRET(l, r);return 0;}BEGCMP(pcharcomp){DEFLR(char);CMPRET(l, r);return 0;}BEGCMP(pdoublecomp){DEFLR(double);CMPRET(l, r);return 0;}int32_t pstrcomp (const void *left, const void *right) {char* l = *(char**)left;char* r = *(char**)right;return strcmp(l, r);}BEGCMP(phwllABcomp){DEFLR(hwll);CMPRET(l.a, r.a);CMPRET(l.b, r.b);return 0;}BEGCMP(phwllREVcomp){DEFLR(hwll);CMPRET(l.b, r.b);CMPRET(l.a, r.a);return 0;}BEGCMP(ptriplecomp){DEFLR(hwllc);CMPRET(l.a, r.a);CMPRET(l.b, r.b);CMPRET(l.c, r.c);return 0;}BEGCMP(ptripleREVcomp){DEFLR(hwllc);CMPRET(l.b, r.b);CMPRET(l.a, r.a);CMPRET(l.c, r.c);return 0;}BEGCMP(ptripleCABcomp){DEFLR(hwllc);CMPRET(l.c, r.c);CMPRET(l.a, r.a);CMPRET(l.b, r.b);return 0;}BEGCMP(phwrealcomp){DEFLR(hwreal);CMPRET(l.a, r.a);CMPRET(l.b, r.b);return 0;}int32_t pquadcomp (const void *left, const void *right) {linell l = *(linell*)left;linell r = *(linell*)right;sll ac = phwllABcomp(&(l.a), &(r.a));if (ac) return ac;sll bc = phwllABcomp(&(l.b), &(r.b));if (bc) return bc;return 0;}int32_t pfracomp (const void *left, const void *right) {hwllc l = *(hwllc*)left;hwllc r = *(hwllc*)right;CMPRET(l.a * r.b, l.b * r.a);return 0;}bool isinrange (sll left, sll x, sll right) {return (left <= x && x <= right);}bool isinrange_soft (sll left, sll x, sll right) {return (left <= x && x <= right) || (left >= x && x >= right);}void sw (sll *l, sll *r) {sll t = *l;*l = *r;*r = t;}ull frac[N_MAX * 3], invf[N_MAX * 3];ull ncr (sll n, sll r, ull m) {if (n < 0 || r < 0 || n < r) return 0;return frac[n] * (invf[r] * invf[n - r] % m) % m;}sll a[N_MAX + 5];// ull a[N_MAX + 5];// sll a[3001][3001];sll b[N_MAX + 5];// ull b[N_MAX + 5];// sll b[3001][3001];sll c[N_MAX + 5];sll d[N_MAX + 5];sll e[N_MAX * 4];char s[N_MAX + 1];// char s[3010][3010];char t[N_MAX + 1];// char t[3010][3010];char u[N_MAX + 1];hwll xy[N_MAX + 5];hwllc tup[N_MAX + 5];sll table[3005][3005];ull gin[N_MAX];// here we gobool isr[N_MAX];ull lbit[N_MAX], rbit[N_MAX], kmax = 235;ull rpress[N_MAX];ull rseq[N_MAX];void shift (ull a[], ull x) {sll j;if (!x) return;if (x & 63LL) {ull up = (x >> 6);ull down = (x & 63LL);for (j = kmax - 1; ; j--) {a[j] |= (a[j - up] << down);if (j <= up) break;a[j] |= (a[j - up - 1] >> (64 - down));}} else {sll y = (x >> 6);for (j = kmax - 1; j >= y; j--) a[j] |= a[j - y];}}void go (sll l, sll r) {sll i, j;for (i = 0; i < n; i++) {isr[i] = false;}for (i = l; i < r; i++) {isr[d[i]] = true;}ull rlen = 0;for (i = 0; i < n; i++) {if (isr[i]) {rseq[rlen] = a[i];rpress[i] = rlen++;}}for (i = 0; i < kmax; i++) lbit[i] = 0LL;lbit[0] = 1LL;for (i = 0; i < n; i++) {if (isr[i]) continue;shift(lbit, a[i]);}// for (i = 0; i < 10; i++) {// printf("lbit %lld: %lld\n", i, lbit[i]);// }// fflush(stdout);for (i = l; i < r; i++) {rseq[rpress[d[i]]] = e[i];for (j = 0; j < kmax; j++) rbit[j] = lbit[j];for (j = 0; j < rlen; j++) {shift(rbit, rseq[j]);// printf("shift: %lld\n", rseq[j]);}// for (j = 0; j < 10; j++) {// printf("rbit %lld: %lld\n", j, rbit[j]);// }// for (j = 0; j < 64; j++) {// printf("rbit <%lld>: %lld\n", j, (rbit[0] >> j) % 2);// }if (rbit[k >> 6] & (1LL << (k & 63LL))) {puts("1");} else {puts("0");}}}ull solve () {sll i, j, ki, li;// ull result = 0;sll result = 0;double dresult = 0;// ull maybe = 0;sll maybe = 0;// ull sum = 0;sll sum = 0;sll item;sll *dpcell;ull B = 110;i = 0;while (i < q) {j = smin(i + B, q);go(i, j);while (i < j) {a[d[i]] = e[i];i++;}}// printf("%lld\n", result);// printf("%.15f\n", dresult);// puts(s);return 0;success:// puts("YES");puts("Yes");// printf("%llu\n", result);// puts("0");// puts("First");return 0;fail:// puts("NO");puts("No");// puts("0");// puts("-1");// puts("-1 -1 -1");// puts("Second");return 1;}int32_t main (int argc, char *argv[]) {int32_t i, j;n = 4;m = 0;// scanf("%llu", &m);// scanf("%llu%llu", &h, &w);scanf("%llu", &n, &m);scanf("%llu", &k, &n, &m);// scanf("%llu%llu", &h, &w);// scanf("%llu", &q);// scanf("%lld%lld", &va, &vb, &vc, &vd);// va--;// vb--;// scanf("%llu%llu%llu%llu", &ua, &ub, &uc, &ud, &ue);// scanf("%s", s);// scanf("%s", t);// scanf("%s", u);// scanf("%llu", &k);// scanf("%lld", &m);// for (i = 0; i < n; i++) {// // scanf("%lld", &a[i]);// scanf("%lld", &d[i]);// }// scanf("%llu", &q);for (i = 0; i < n; i++) {// scanf("%lld%lld", &xy[i].a, &xy[i].b);// scanf("%lld%lld%lld", &tup[i].a, &tup[i].b, &tup[i].c);// scanf("%lld", &c[i]);scanf("%lld", &a[i]);// scanf("%lld", &b[i]);// scanf("%lld", &c[i]);// scanf("%lld", &d[i]);// a[i]--;// b[i]--;// c[i]--;// d[i]--;// xy[i].a--;// xy[i].b--;// tup[i].a--;// tup[i].b--;}// scanf("%llu", &m);scanf("%llu", &q);for (i = 0; i < q; i++) {// scanf("%lld%lld", &a[i], &b[i]);// scanf("%lld", &b[i]);// a[i]--;// b[i]--;// scanf("%lld", &c[i]);scanf("%lld", &d[i]);scanf("%lld", &e[i]);// c[i]--;d[i]--;}// for (i = 0; i < q; i++) {// // scanf("%lld%lld", &xy[i].a, &xy[i].b);// scanf("%lld", &c[i]);// // xy[i].a--;// // xy[i].b--;// }// for (i = 0; i < h; i++) {// for (j = 0; j < w; j++) {// scanf("%lld", &table[i][j]);// // table[i][j]--;// }// }// for (i = 0; i < h; i++) {// scanf("%s", s[i]);// }// scanf("%llu", &q);solve();return 0;}