結果

問題 No.206 数の積集合を求めるクエリ
ユーザー antaanta
提出日時 2015-05-27 22:58:10
言語 Perl
(5.38.2)
結果
AC  
実行時間 139 ms / 7,000 ms
コード長 9,361 bytes
コンパイル時間 3,693 ms
コンパイル使用メモリ 159,344 KB
実行使用メモリ 6,812 KB
最終ジャッジ日時 2023-09-20 16:51:22
合計ジャッジ時間 9,202 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
外部呼び出し有り
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 109 ms
6,100 KB
testcase_01 AC 109 ms
5,956 KB
testcase_02 AC 109 ms
5,884 KB
testcase_03 AC 109 ms
6,028 KB
testcase_04 AC 108 ms
5,944 KB
testcase_05 AC 109 ms
6,016 KB
testcase_06 AC 109 ms
6,036 KB
testcase_07 AC 108 ms
5,984 KB
testcase_08 AC 109 ms
6,160 KB
testcase_09 AC 109 ms
6,040 KB
testcase_10 AC 109 ms
5,980 KB
testcase_11 AC 108 ms
5,956 KB
testcase_12 AC 110 ms
5,976 KB
testcase_13 AC 109 ms
5,972 KB
testcase_14 AC 110 ms
6,020 KB
testcase_15 AC 109 ms
5,964 KB
testcase_16 AC 109 ms
6,024 KB
testcase_17 AC 130 ms
6,668 KB
testcase_18 AC 120 ms
6,728 KB
testcase_19 AC 127 ms
6,744 KB
testcase_20 AC 119 ms
6,308 KB
testcase_21 AC 122 ms
6,640 KB
testcase_22 AC 121 ms
6,448 KB
testcase_23 AC 128 ms
6,720 KB
testcase_24 AC 139 ms
6,656 KB
testcase_25 AC 135 ms
6,664 KB
testcase_26 AC 127 ms
6,812 KB
testcase_27 AC 122 ms
6,348 KB
testcase_28 AC 129 ms
6,484 KB
testcase_29 AC 130 ms
6,588 KB
testcase_30 AC 127 ms
6,384 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.pl syntax OK

ソースコード

diff # 

system './' . $exe_name;

BEGIN {
    $exe_name = $^O eq 'MSWin32' ? 'a.exe' : 'a.out';
    return if -e $exe_name;
    open my $fh, '>', 'tmp.cpp';
    print $fh <<'CODE';
#line 8
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <limits>
#include <functional>

#include <cstdint>

#ifdef NDEBUG
#undef NDEBUG
#endif
#include <cassert>

#include <nmmintrin.h>
#if defined(_MSC_VER)
#include <intrin.h>
#endif

#ifdef _DEBUG
#undef assert
#include "C:\Dropbox\backup\implements\Util\MyAssert.hpp"
#define assert my_assert
#else
#undef assert
#define assert(x) 
#endif

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

#ifdef _MSC_VER
#define alignas(x) __declspec(align(x))
#endif

template<typename R_>
//typedef int R;
struct IntOpDefault {
    typedef R_ R;
    static void copy(R *res, const R *p, int n) {
        for(int i = 0; i < n; ++ i)
            res[i] = p[i];
    }

    static void fill_zero(R *p, int n) {
        for(int i = 0; i < n; ++ i)
            p[i] = R();
    }

    static void negate_all(R *res, const R *p, int n) {
        for(int i = 0; i < n; ++ i)
            res[i] = -p[i];
    }

    static void convolute_schoolbook(R *res, const R *p, int pn, const R *q, int qn) {
        fill_zero(res, pn + qn - 1);
        for(int i = 0; i < pn; ++ i)
            for(int j = 0; j < qn; ++ j)
                res[i + j] += p[i] * q[j];
    }

    static void add(R *res, const R *p, int n) {
        for(int i = 0; i < n; ++ i)
            res[i] += p[i];
    }

    static void subtract(R *res, const R *p, int n) {
        for(int i = 0; i < n; ++ i)
            res[i] -= p[i];
    }

    static R inverse(R x) {
        R i = x, p, TWO = R(2), ONE = R(1);
        do {
            p = i * x;
            i *= TWO - p;
        }while(!(p == ONE));
        return i;
    }

    static void multiply_scalar(R *p, int n, R scalar) {
        for(int i = 0; i < n; ++ i)
            p[i] *= scalar;
    }
};

struct u32x4 {
    __m128i v;
    u32x4(): v(_mm_setzero_si128()) { }
    u32x4(const __m128i &v_): v(v_) { }

    static u32x4 set1(uint32_t x) {
        return u32x4(_mm_set1_epi32(x));
    }
    template<typename T> static u32x4 loadu(const T *p) {
        return u32x4(_mm_loadu_si128(reinterpret_cast<const __m128i*>(p)));
    }
    template<typename T> void storeu(T *p) const {
        _mm_storeu_si128(reinterpret_cast<__m128i*>(p), v);
    }

    u32x4 operator*(const u32x4 &that) const {
        return u32x4(_mm_mullo_epi32(v, that.v));
    }
    u32x4 operator+(const u32x4 &that) const {
        return u32x4(_mm_add_epi32(v, that.v));
    }
    u32x4 operator-(const u32x4 &that) const {
        return u32x4(_mm_sub_epi32(v, that.v));
    }
    u32x4 &operator+=(const u32x4 &that) {
        return *this = *this + that;
    }

    template<int s> u32x4 slli() const {
        return u32x4(_mm_slli_si128(v, s));
    }
    u32x4 slli4() const { return slli<4>(); }
    u32x4 slli8() const { return slli<8>(); }
    u32x4 slli12() const { return slli<12>(); }

    template<int s> u32x4 srli() const {
        return u32x4(_mm_srli_si128(v, s));
    }

    u32x4 srli4() const { return srli<4>(); }
    u32x4 srli8() const { return srli<8>(); }
    u32x4 srli12() const { return srli<12>(); }
};

template<int PN_of_4, int QN_of_4>
inline void add_template(uint32_t *res, const uint32_t *p, const uint32_t *q) {
    static_assert(PN_of_4 >= QN_of_4, "PN_of_4 >= QN_of_4");
    for(int i = 0; i < QN_of_4; ++ i) {
        u32x4 sum = u32x4::loadu(p + i * 4) + u32x4::loadu(q + i * 4);
        sum.storeu(res + i * 4);
    }
    for(int i = QN_of_4 * 4; i < PN_of_4 * 4; ++ i)
        res[i] = p[i];
}
template<int N_of_4>
inline void add_template(uint32_t *p, const uint32_t *q) {
    for(int i = 0; i < N_of_4; ++ i) {
        u32x4 sum = u32x4::loadu(p + i * 4) + u32x4::loadu(q + i * 4);
        sum.storeu(p + i * 4);
    }
}

template<int PN_of_4, int QN_of_4>
inline void subtract_template(uint32_t *res, const uint32_t *p, const uint32_t *q) {
    static_assert(PN_of_4 >= QN_of_4, "PN_of_4 >= QN_of_4");
    for(int i = 0; i < QN_of_4; ++ i) {
        u32x4 diff = u32x4::loadu(p + i * 4) - u32x4::loadu(q + i * 4);
        diff.storeu(res + i * 4);
    }
    for(int i = QN_of_4 * 4; i < PN_of_4 * 4; ++ i)
        res[i] = p[i];
}
template<int N_of_4>
inline void subtract_template(uint32_t *p, const uint32_t *q) {
    for(int i = 0; i < N_of_4; ++ i) {
        u32x4 diff = u32x4::loadu(p + i * 4) - u32x4::loadu(q + i * 4);
        diff.storeu(p + i * 4);
    }
}

struct IntOp32 : IntOpDefault<IntOp32> {
    uint32_t x;
    IntOp32(): x(0) { }
    explicit IntOp32(uint32_t x_): x(x_) { }

    IntOp32 &operator+=(const IntOp32 &that) { x += that.x; return *this; }
    IntOp32 &operator-=(const IntOp32 &that) { x -= that.x; return *this; }
    IntOp32 &operator*=(const IntOp32 &that) { x *= that.x; return *this; }

    IntOp32 operator+(const IntOp32 &that) const { return IntOp32(x + that.x); }
    IntOp32 operator-(const IntOp32 &that) const { return IntOp32(x - that.x); }
    IntOp32 operator*(const IntOp32 &that) const { return IntOp32(x * that.x); }
    IntOp32 operator-() const { return IntOp32(~x + 1); }

    bool operator==(const IntOp32 &that) const { return x == that.x; }

    //resは (PN_of_4 + QN_of_4) * 4 のサイズを書き込む
    template<int PN_of_4, int QN_of_4>
    static void convolute_schoolbook_template(uint32_t *res, const uint32_t *p, const uint32_t *q) {
        u32x4 sum[PN_of_4 + QN_of_4];

        for(int i = 0; i < PN_of_4; ++ i) {
            u32x4 x0 = u32x4::set1(p[i * 4 + 0]);
            u32x4 x1 = u32x4::set1(p[i * 4 + 1]);
            u32x4 x2 = u32x4::set1(p[i * 4 + 2]);
            u32x4 x3 = u32x4::set1(p[i * 4 + 3]);

            for(int j = 0; j < QN_of_4; ++ j) {
                u32x4 y = u32x4::loadu(q + j * 4);
                u32x4 z0 = x0 * y;
                u32x4 z1 = x1 * y;
                u32x4 z2 = x2 * y;
                u32x4 z3 = x3 * y;

                sum[i + j + 0] += (z0 + z1.slli4()) + (z2.slli8() + z3.slli12());
                sum[i + j + 1] += (z1.srli8() + z2.srli4() + z3).srli4();
            }
        }

        for(int i = 0; i < PN_of_4 + QN_of_4; ++ i)
            sum[i].storeu(res + i * 4);
    }

    enum { KARATSUBA_THRESHOLD_OF_4 = 4 };

#define ENABLE_KARATSUBA(PNo4, QNo4) \
    ((PNo4) >= KARATSUBA_THRESHOLD_OF_4 && (QNo4) >= KARATSUBA_THRESHOLD_OF_4)

    template<int PNo4, int QNo4>
    static typename enable_if<ENABLE_KARATSUBA(PNo4,QNo4)>::type convolute_template(uint32_t *res, const uint32_t *p, const uint32_t *q) {
        enum { LOo4 = (PNo4 + 1) / 2, HPo4 = PNo4 - LOo4, HQo4 = QNo4 - LOo4 };
        static_assert(0 < LOo4 && 0 < HQo4 && HPo4 <= LOo4 && HQo4 <= LOo4, "parameters");
        uint32_t t0[LOo4 * 4], t1[LOo4 * 4], r1[LOo4 * 4 * 2];
        uint32_t * const r0 = res, * const rinf = res + LOo4 * 4 * 2;
        add_template<LOo4, HPo4>(t0, p, p + LOo4 * 4);
        add_template<LOo4, HQo4>(t1, q, q + LOo4 * 4);
        convolute_template<LOo4, LOo4>(r1, t0, t1);
        convolute_template<LOo4, LOo4>(r0, p, q);
        convolute_template<HPo4, HQo4>(rinf, p + LOo4 * 4, q + LOo4 * 4);
        subtract_template<LOo4 * 2>(r1, r0);
        subtract_template<HPo4 + HQo4>(r1, rinf);
        add_template<LOo4 * 2>(res + LOo4 * 4, r1);
    }

    template<int PNo4, int QNo4>
    static typename enable_if<!ENABLE_KARATSUBA(PNo4,QNo4)>::type convolute_template(uint32_t *res, const uint32_t *p, const uint32_t *q) {
        return convolute_schoolbook_template<PNo4,QNo4>(res, p, q);
    }

#undef ENABLE_KARATSUBA
};

alignas(16) uint32_t p[100000], q[100000], res[200000];
int main() {
    int L, M, N;
    scanf("%d%d%d", &L, &M, &N);
    rep(i, L) {
        int a;
        scanf("%d", &a), -- a;
        p[N-1-a] = 1;
    }
    rep(i, M) {
        int b;
        scanf("%d", &b), -- b;
        q[b] = 1;
    }
    IntOp32::convolute_template<100000/4,100000/4>(res, p, q);
    int Q;
    scanf("%d", &Q);
    rep(i, Q) {
        int ans = res[N-1-i];
        printf("%d\n", ans);
    }
    return 0;
}
CODE
    system "g++ -m64 -O2 -lm -mavx -std=c++11 tmp.cpp -o $exe_name 2> my_compile.log";
    if($? != 0) {
        open(my $fh, '<', 'my_compile.log');
        while(<$fh>) { print STDERR $_; }
        die 'compile error';
    }
}
0