結果
問題 | No.202 1円玉投げ |
ユーザー |
![]() |
提出日時 | 2015-06-01 02:01:27 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 80 ms / 5,000 ms |
コード長 | 1,900 bytes |
コンパイル時間 | 904 ms |
コンパイル使用メモリ | 85,932 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-22 09:22:59 |
合計ジャッジ時間 | 2,698 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:63:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 63 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:68:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 68 | scanf("%d %d", &x, &y); | ~~~~~^~~~~~~~~~~~~~~~~
ソースコード
#include <cassert>#include <functional>#include <set>#include <ctime>#include <cmath>#include <climits>#include <string>#include <queue>#include <map>#include <vector>#include <algorithm>#include <iostream>#include <cstdio>#ifndef ONLINE_JUDGE //POJ# include <random># include <array># define mkt make_tuple# define empb emplace_back#endif#ifdef _LOCAL# include "for_local.h"#endifusing namespace std;typedef unsigned int uint; typedef unsigned long long ull;#define repi(_I, _B, _E) for(int _I = (_B); (_I) < (_E); ++ (_I))#define rep(_I, _N) for(int _I = 0; (_I) < (_N); ++ (_I))#define mkp make_pair#define all(_X) (_X).begin(), (_X).end()#define scani(_V) std::scanf("%d", &_V)#define printi(_V) std::printf("%d", static_cast<int>(_V))#include <list>template<typename T>T selfprod(T const& x, T const& y) { return x * x + y * y; }int const INF = 1 << 29;int const B = 40; //bucket sizevector<vector<pair<int,int>>> bs(20001 / B + 1);bool conflict(int i, int x, int y) {if ( !(0 <= i && i < bs.size()) ) return false;auto& b = bs[i];auto lb = lower_bound(all(b), mkp(x - 20, 0));auto ub = upper_bound(all(b), mkp(x + 20, INF));for ( ; lb != ub; ++lb ) {auto& p = *lb;if ( selfprod(x - p.first, y - p.second) < 400 ) return true;}return false;}bool conflict(int x, int y) {int yl = max((y - 20) / B, 0);int yr = min((y + 20 + B - 1) / B, (int)bs.size());//assert(yr - yl <= 2);for ( int i = yl; i < yr; ++i ) {if ( conflict(i, x, y) ) return true;}return false;}signed main() {int n;scanf("%d", &n);int k = 0;rep(i, n) {int x, y;scanf("%d %d", &x, &y);if ( !conflict(x, y) ) {//bs[i]: y座標が [i*B, (i+1)*B) に入る点全体をもつ。x座標について整列済み。bs[y / B].emplace(lower_bound(all(bs[y / B]), mkp(x, y)), mkp(x, y));++k;}}printf("%d\n", k);return 0;}