結果

問題 No.896 友達以上恋人未満
ユーザー kcvlexkcvlex
提出日時 2019-09-27 23:08:47
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2,297 ms / 3,500 ms
コード長 3,697 bytes
コンパイル時間 1,633 ms
コンパイル使用メモリ 168,704 KB
実行使用メモリ 174,264 KB
最終ジャッジ日時 2023-10-25 06:02:41
合計ジャッジ時間 15,767 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 555 ms
135,344 KB
testcase_01 AC 555 ms
135,344 KB
testcase_02 AC 580 ms
135,344 KB
testcase_03 AC 564 ms
135,344 KB
testcase_04 AC 579 ms
135,344 KB
testcase_05 AC 1,343 ms
151,736 KB
testcase_06 AC 2,297 ms
151,728 KB
testcase_07 AC 1,327 ms
151,736 KB
testcase_08 AC 1,359 ms
151,736 KB
testcase_09 AC 1,795 ms
168,120 KB
testcase_10 AC 1,983 ms
174,264 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:59:17: warning: 'pre_b' may be used uninitialized [-Wmaybe-uninitialized]
   59 | #define scast64 static_cast<int64_t>
      |                 ^~~~~~~~~~~
main.cpp:94:20: note: 'pre_b' was declared here
   94 |     int32_t pre_a, pre_b;
      |                    ^~~~~
main.cpp:59:17: warning: 'pre_a' may be used uninitialized [-Wmaybe-uninitialized]
   59 | #define scast64 static_cast<int64_t>
      |                 ^~~~~~~~~~~
main.cpp:94:13: note: 'pre_a' was declared here
   94 |     int32_t pre_a, pre_b;
      |             ^~~~~
main.cpp:59:17: warning: 'pre_y' may be used uninitialized [-Wmaybe-uninitialized]
   59 | #define scast64 static_cast<int64_t>
      |                 ^~~~~~~~~~~
main.cpp:71:20: note: 'pre_y' was declared here
   71 |     int32_t pre_x, pre_y;
      |                    ^~~~~
main.cpp:59:17: warning: 'pre_x' may be used uninitialized [-Wmaybe-uninitialized]
   59 | #define scast64 static_cast<int64_t>
      |                 ^~~~~~~~~~~
main.cpp:71:13: note: 'pre_x' was declared here
   71 |     int32_t pre_x, pre_y;
      |             ^~~~~

ソースコード

diff # 

// #define DEBUGGING
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = int64_t;
using ull = uint64_t;
using PLL = pair<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); }

namespace init__ {

struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

}

#ifdef DEBUGGING
// #include "../debug/debug.cpp"
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

template <typename T>
T make_v(T init) { return init; }

template <typename T, typename... Tail>
auto make_v(T init, size_t s, Tail... tail) {
#define rec make_v(init, tail...)
    return V<decltype(rec)>(s, rec);
#undef rec
}

const ssize_t size = (1 << 24) + 10;
const ssize_t input_size = 1e3;
int32_t x[size];
int64_t sum_x[size];
int32_t X[input_size], Y[input_size], A[input_size], B[input_size], ans_pre[input_size];

#define scast64 static_cast<int64_t>
#define cast32 (int32_t)

int main() {
    int32_t M, N, mulX, addX, mulY, addY, MOD;
    cin >> M >> N
        >> mulX >> addX
        >> mulY >> addY
        >> MOD;
    int32_t *ptr_arr[] = { X, Y, A, B, };
    for(int32_t i = 0; i < 4; i++) for(int32_t j = 0; j < M; j++) cin >> ptr_arr[i][j];

    int32_t pre_x, pre_y;
    for(int32_t i = 0; i < N; i++) {
        int32_t nxt_x;
        int32_t nxt_y;
        if(i < M) {
            nxt_x = X[i];
            nxt_y = Y[i];
        } else {
            nxt_x = cast32((scast64(pre_x) * scast64(mulX) + scast64(addX)) % scast64(MOD));
            nxt_y = cast32((scast64(pre_y) * scast64(mulY) + scast64(addY)) % scast64(MOD));
        }
        x[nxt_x] += nxt_y;
        pre_x = nxt_x;
        pre_y = nxt_y;
    }

    for(int i = 1; i < size; i++) {
        for(int j = 1; scast64(i) * scast64(j) < scast64(size); j++) {
            sum_x[i] += x[i * j];
            DEBUG(sum_x[i]);
        }
    }

    int32_t pre_a, pre_b;
    int64_t sum = 0;
    for(int32_t i = 0; i < N; i++) {
        int32_t nxt_a, nxt_b;
        int64_t ans = 0;
        if(i < M) {
            nxt_a = A[i];
            nxt_b = B[i];
        } else {
            nxt_a = cast32((scast64(pre_a) * scast64(mulX) + scast64(addX + MOD - 1)) % scast64(MOD) + 1);
            nxt_b = cast32((scast64(pre_b) * scast64(mulY) + scast64(addY + MOD - 1)) % scast64(MOD) + 1);
        }
        DEBUG(make_pair(nxt_a, nxt_b));
        ans += sum_x[nxt_a];
        if(scast64(nxt_a) * scast64(nxt_b) < scast64(MOD)) ans -= sum_x[nxt_a * nxt_b];
        if(nxt_b == 0) ans = 0;
        if(i < M) cout << ans << endl;
        DEBUG(ans);
        sum ^= ans;
        pre_a = nxt_a;
        pre_b = nxt_b;
    }
    cout << sum << endl;
    return 0;
}
0