結果
問題 | No.937 Ultra Sword |
ユーザー | kcvlex |
提出日時 | 2019-11-30 00:05:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,548 bytes |
コンパイル時間 | 1,982 ms |
コンパイル使用メモリ | 179,132 KB |
実行使用メモリ | 145,656 KB |
最終ジャッジ日時 | 2024-11-21 03:12:40 |
合計ジャッジ時間 | 167,764 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 206 ms
13,636 KB |
testcase_01 | AC | 366 ms
139,128 KB |
testcase_02 | AC | 471 ms
13,764 KB |
testcase_03 | AC | 812 ms
13,640 KB |
testcase_04 | AC | 1,074 ms
13,644 KB |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | AC | 497 ms
13,760 KB |
testcase_23 | AC | 142 ms
13,640 KB |
testcase_24 | TLE | - |
testcase_25 | TLE | - |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | TLE | - |
testcase_30 | TLE | - |
testcase_31 | TLE | - |
testcase_32 | TLE | - |
testcase_33 | TLE | - |
testcase_34 | TLE | - |
testcase_35 | TLE | - |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
testcase_38 | TLE | - |
testcase_39 | TLE | - |
testcase_40 | TLE | - |
testcase_41 | TLE | - |
testcase_42 | TLE | - |
testcase_43 | TLE | - |
testcase_44 | TLE | - |
testcase_45 | TLE | - |
testcase_46 | TLE | - |
ソースコード
// #define DEBUGGING#include <bits/stdc++.h>#define endl '\n'#define ALL(V) (V).begin(), (V).end()#define ALLR(V) (V).rbegin(), (V).rend()template <typename T> using V = std::vector<T>;template <typename T> using VV = V<V<T>>;using ll = std::int64_t;using ull = std::uint64_t;using PLL = std::pair<ll, ll>;using TLL = std::tuple<ll, 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 std::min(t, var_min(tail...)); }template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::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 std::max(low, std::min(high, t)); }template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); }namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; }#define mv_rec make_v(init, tail...)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) { return V<decltype(mv_rec)>(s, mv_rec); }#undef mv_recusing namespace std;#ifdef DEBUGGING#include "../../debug/debug.cpp"#else#define DEBUG(...) 0#define DEBUG_SEPARATOR_LINE 0#endifusing BS = bitset<64>;using Matrix = V<BS>;tuple<Matrix, ll> gauss_elim(Matrix mat) {ll fcnt = 0;ll upper_row = 0;for(ll col = 0; col < 64; col++) {ll row = -1;for(ll r = upper_row; r < mat.size(); r++) {if(mat[r].test(col)) {row = r;break;}}if(row == -1) {fcnt++;continue;}swap(mat[upper_row], mat[row]);for(ll r = 0; r < mat.size(); r++) {if(r == upper_row) continue;if(!mat[r].test(col)) continue;mat[r] ^= mat[upper_row];}upper_row++;}return make_tuple(mat, fcnt);}int main() {ll N;cin >> N;V<ll> A(N);for(auto &&ele : A) cin >> ele;Matrix mat;auto build = [&](ll n) {BS ret;for(ll j = 0; n; j++) {if(n & 1) ret.set(j, 1);n /= 2;}return ret;};for(ll i = 0; i < N; i++) {ll cur = A[i];for(ll k = 0; k < 32; k++) {mat.push_back(BS(cur));cur *= 2;}}Matrix ret;ll fcnt;tie(ret, fcnt) = gauss_elim(mat);ll rank = ret.size() - fcnt;while(rank < ret.size()) ret.pop_back();V<ll> sum_v(1e5 + 10);ll sum = 0;for(ll e : A) {sum += e;sum_v[e]++;}ll ans = 5e15;for(ll j = 1; j <= 1e5 + 10; j++) {auto cmat = ret;cmat.push_back(BS(j));ll cfcnt;tie(ignore, cfcnt) = gauss_elim(cmat);if(cfcnt == fcnt) {ll tmp = sum;for(ll k = 1; j * k < sum_v.size(); k++) tmp -= sum_v[j * k] * (j * k - k);chmin(ans, tmp);}}cout << ans << endl;return 0;}