結果
問題 | No.202 1円玉投げ |
ユーザー | kimiyuki |
提出日時 | 2017-03-14 22:26:46 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3,272 ms / 5,000 ms |
コード長 | 2,053 bytes |
コンパイル時間 | 1,395 ms |
コンパイル使用メモリ | 150,144 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-08-23 23:33:04 |
合計ジャッジ時間 | 50,346 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3,257 ms
4,376 KB |
testcase_01 | AC | 3,204 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 14 ms
4,376 KB |
testcase_06 | AC | 2,233 ms
4,384 KB |
testcase_07 | AC | 2,795 ms
4,380 KB |
testcase_08 | AC | 2,856 ms
4,380 KB |
testcase_09 | AC | 886 ms
4,376 KB |
testcase_10 | AC | 159 ms
4,380 KB |
testcase_11 | AC | 602 ms
4,376 KB |
testcase_12 | AC | 632 ms
4,380 KB |
testcase_13 | AC | 193 ms
4,380 KB |
testcase_14 | AC | 19 ms
4,376 KB |
testcase_15 | AC | 827 ms
4,380 KB |
testcase_16 | AC | 3,232 ms
4,376 KB |
testcase_17 | AC | 3,231 ms
4,376 KB |
testcase_18 | AC | 3,238 ms
4,376 KB |
testcase_19 | AC | 724 ms
4,376 KB |
testcase_20 | AC | 1,809 ms
4,376 KB |
testcase_21 | AC | 715 ms
4,376 KB |
testcase_22 | AC | 2 ms
4,380 KB |
testcase_23 | AC | 2 ms
4,380 KB |
testcase_24 | AC | 2 ms
4,380 KB |
testcase_25 | AC | 2 ms
4,380 KB |
testcase_26 | AC | 2 ms
4,376 KB |
testcase_27 | AC | 2 ms
4,380 KB |
testcase_28 | AC | 2 ms
4,380 KB |
testcase_29 | AC | 2 ms
4,376 KB |
testcase_30 | AC | 2 ms
4,376 KB |
testcase_31 | AC | 2 ms
4,380 KB |
testcase_32 | AC | 2 ms
4,376 KB |
testcase_33 | AC | 2 ms
4,376 KB |
testcase_34 | AC | 2 ms
4,376 KB |
testcase_35 | AC | 3,263 ms
4,376 KB |
testcase_36 | AC | 3,269 ms
4,380 KB |
testcase_37 | AC | 3,272 ms
4,380 KB |
testcase_38 | AC | 3,249 ms
4,380 KB |
testcase_39 | AC | 1 ms
4,376 KB |
testcase_40 | AC | 2 ms
4,376 KB |
ソースコード
#pragma GCC optimize "O3" #pragma GCC target "tune=native" #pragma GCC target "avx" #include <cstdio> #include <algorithm> #include <immintrin.h> #define repeat(i,n) for (int i = 0; (i) < int(n); ++(i)) using namespace std; template <class T> inline T sq(T x) { return x*x; } constexpr int max_n = 100000; constexpr int r = 10; __attribute__((aligned(32))) int32_t x[max_n]; __attribute__((aligned(32))) int32_t y[max_n]; __attribute__((aligned(32))) int32_t z[max_n]; // is_removed int main() { int n; scanf("%d", &n); repeat (i,n) scanf("%d%d", &x[i], &y[i]); int i = 0; for (; i+3 < n; i += 4) { const __m128i xi = _mm_load_si128((__m128i *)(x + i)); const __m128i yi = _mm_load_si128((__m128i *)(y + i)); __m128i zi = _mm_setzero_si128(); repeat (j,i) { __m128i xj = _mm_set1_epi32(x[j]); __m128i yj = _mm_set1_epi32(y[j]); __m128i zj = _mm_set1_epi32(not z[j]); xj = _mm_sub_epi32(xj, xi); yj = _mm_sub_epi32(yj, yi); xj = _mm_mullo_epi32(xj, xj); yj = _mm_mullo_epi32(yj, yj); const __m128i d = _mm_add_epi32(xj, yj); const __m128i e = _mm_set1_epi32(sq(r + r)); __m128i cmp = _mm_cmplt_epi32(d, e); zi = _mm_add_epi32(zi, _mm_mullo_epi32(cmp, zj)); } _mm_store_si128((__m128i *)(z + i), zi); repeat (di, 4) { if (z[i+di]) { z[i+di] = 1; } else { repeat (dj, di) { if (not z[i+dj] and sq(x[i+dj] - x[i+di]) + sq(y[i+dj] - y[i+di]) < sq(r + r) ) { z[i+di] = 1; break; } } } } } for (; i < n; ++ i) { repeat (j,i) { if (not z[j] and sq(x[j] - x[i]) + sq(y[j] - y[i]) < sq(r + r) ) { z[i] = 1; break; } } } int cnt = count(z, z + n, 0); printf("%d\n", cnt); return 0; }