結果

問題 No.9 モンスターのレベル上げ
ユーザー antaanta
提出日時 2015-01-28 04:15:19
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 9,050 bytes
コンパイル時間 841 ms
コンパイル使用メモリ 90,252 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2024-06-23 03:35:55
合計ジャッジ時間 2,603 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
7,680 KB
testcase_01 AC 4 ms
7,936 KB
testcase_02 AC 124 ms
7,936 KB
testcase_03 WA -
testcase_04 AC 57 ms
7,936 KB
testcase_05 AC 39 ms
7,680 KB
testcase_06 AC 16 ms
7,808 KB
testcase_07 AC 4 ms
7,808 KB
testcase_08 AC 19 ms
7,808 KB
testcase_09 AC 121 ms
7,808 KB
testcase_10 AC 4 ms
7,808 KB
testcase_11 AC 96 ms
7,808 KB
testcase_12 AC 92 ms
8,064 KB
testcase_13 WA -
testcase_14 AC 118 ms
7,936 KB
testcase_15 AC 109 ms
7,808 KB
testcase_16 WA -
testcase_17 AC 72 ms
7,936 KB
testcase_18 AC 59 ms
7,936 KB
testcase_19 AC 5 ms
7,808 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:327:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  327 |         scanf("%d", &N);
      |         ~~~~~^~~~~~~~~~
main.cpp:330:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  330 |                 scanf("%d", &A[i]);
      |                 ~~~~~^~~~~~~~~~~~~
main.cpp:334:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  334 |                 scanf("%d", &B[i]);
      |                 ~~~~~^~~~~~~~~~~~~

ソースコード

diff # 

#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 <cassert>
#include <limits>
#include <functional>
#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; }


namespace vEB_tree {
	static int bsf(unsigned long long x) {
#if defined(__GNUC__)
		return __builtin_ctzll(x);
#else
		int r = 0;
		x &= ~x + 1;
		if(x & 0xffffffff00000000ULL) r += 32;
		if(x & 0xffff0000ffff0000ULL) r += 16;
		if(x & 0xff00ff00ff00ff00ULL) r += 8;
		if(x & 0xf0f0f0f0f0f0f0f0ULL) r += 4;
		if(x & 0xccccccccccccccccULL) r += 2;
		if(x & 0xaaaaaaaaaaaaaaaaULL) r += 1;
		return r;
#endif
	}

	static int bsr(unsigned long long x) {
#if defined(__GNUC__)
		return 63 - __builtin_clzll(x);
#else
		int r = 0;
		if(x & 0xffffffff00000000ULL) x >>= 32, r += 32;
		if(x &         0xffff0000U  ) x >>= 16, r += 16;
		if(x &             0xff00U  ) x >>= 8,  r += 8;
		if(x &               0xf0U  ) x >>= 4,  r += 4;
		if(x &                0xcU  ) x >>= 2,  r += 2;
		if(x &                0x2U  )           r += 1;
		return r;
#endif
	}

	//M = 2^6
	struct NodeLv0 {
		static const int M = 1 << 6;
		unsigned long long bits;

		NodeLv0() { }

		void clear() {
			bits = 0;
		}

		bool empty() const { return bits == 0; }
		int getMin() const { return empty() ?  M : bsf(bits); }
		int getMax() const { return empty() ? -1 : bsr(bits); }

		bool get(int i) const {
			return bits >> i & 1;
		}

		bool insert(int i) {
			bool r = bits == 0;
			bits |= 1ULL << i;
			return r;
		}

		bool remove(int i) {
			unsigned long long mask = 1ULL << i;
			bool r = bits == mask;
			bits &= ~mask;
			return r;
		}

		int findNext(int i) const {
			unsigned long long x = bits >> i;
			if(i >= M || x == 0) return M;
			return i + bsf(x);
		}

		int findPrev(int i) const {
			unsigned long long x = bits << (M - 1 - i);
			if(i < 0 || x == 0) return -1;
			return i - (M - 1 - bsr(x));
		}
	};
	//M = 2^12
	struct NodeLv1 {
		static const int SqrtM = 1 << 6, M = SqrtM * SqrtM;
		short bounds[2];
		NodeLv0 children[SqrtM];
		NodeLv0 summary;

		NodeLv1() { }
		
		void clear() {
			bounds[0] = M;
			bounds[1] = -1;
			for(int i = 0; i < SqrtM; ++ i)
				children[i].clear();
			summary.clear();
		}

		bool empty() const { return bounds[1] == -1; }
		int getMin() const { return bounds[0]; }
		int getMax() const { return bounds[1]; }

		bool get(int i) const {
			return
				bounds[0] == i || bounds[1] == i ||
				children[i / SqrtM].get(i % SqrtM);
		}

		bool insert(int i) {
			int lo = bounds[0], up = bounds[1];
			if(up <= i) {
				if(i == up) return false;
				bounds[1] = i;
				if(up == -1) {
					bounds[0] = i;
					return true;
				}
				if(lo == up)
					return false;
				i = up;
			}else if(i <= lo) {
				if(i == lo) return false;
				bounds[0] = i;
				if(lo == up) 
					return false;
				i = lo;
			}
			int child = i / SqrtM, rem = i % SqrtM;
			if(children[child].insert(rem))
				summary.insert(child);
			return false;
		}

		bool remove(int i) {
			int lo = bounds[0], up = bounds[1];
			if(i <= lo) {
				if(i < lo) return false;
				if(lo == up) {
					bounds[0] = M;
					bounds[1] = -1;
					return true;
				}
				int minChild = summary.getMin();
				if(minChild == SqrtM) {
					bounds[0] = up;
					return false;
				}
				bounds[0] = i = minChild * SqrtM + children[minChild].getMin();
			}else if(up <= i) {
				if(up < i) return false;
				int maxChild = summary.getMax();
				if(maxChild == -1) {
					bounds[1] = lo;
					return false;
				}
				bounds[1] = i = maxChild * SqrtM + children[maxChild].getMax();
			}
			int child = i / SqrtM, rem = i % SqrtM;
			if(children[child].remove(rem))
				summary.remove(child);
			return false;
		}

		int findNext(int i) const {
			if(M <= i) return M;
			int lo = bounds[0];
			if(i <= lo) return lo;
			int child = i / SqrtM, rem = i % SqrtM;
			if(rem <= children[child].getMax()) {
				return child * SqrtM + children[child].findNext(rem);
			}else {
				int nextChild = summary.findNext(child + 1);
				if(nextChild == SqrtM) {
					int hi = bounds[1];
					return i <= hi ? hi : M;
				}
				return nextChild * SqrtM + children[nextChild].getMin();
			}
		}

		int findPrev(int i) const {
			if(i < 0) return -1;
			int hi = bounds[1];
			if(hi <= i) return hi;
			int child = i / SqrtM, rem = i % SqrtM;
			if(children[child].getMin() <= rem) {
				return child * SqrtM + children[child].findPrev(rem);
			}else {
				int prevChild = summary.findPrev(child - 1);
				if(prevChild == -1) {
					int lo = bounds[0];
					return lo <= i ? lo : -1;
				}
				return prevChild * SqrtM + children[prevChild].getMax();
			}
		}
	};
	//M = 2^24
	struct NodeLv2 {
		static const int SqrtM = 1 << 12, M = SqrtM * SqrtM;
		NodeLv1 children[SqrtM];
		NodeLv1 summary;

		NodeLv2() { }

		void clear() {
			for(int i = 0; i < SqrtM; i ++)
				children[i].clear();
			summary.clear();
		}

		bool empty() const { return summary.empty(); }

		int getMin() const {
			int child = summary.getMin();
			return child == SqrtM ? M : child * SqrtM + children[child].getMin();
		}

		int getMax() const {
			int child = summary.getMax();
			return child == -1 ? -1 : child * SqrtM + children[child].getMax();
		}

		bool get(int i) const {
			return children[i / SqrtM].get(i % SqrtM);
		}

		void insert(int i) {
			int child = i / SqrtM, rem = i % SqrtM;
			if(children[child].insert(rem))
				summary.insert(child);
		}

		void remove(int i) {
			int child = i / SqrtM, rem = i % SqrtM;
			if(children[child].remove(rem))
				summary.remove(child);
		}

		int findNext(int i) const {
			if(M <= i) return M;
			int child = i / SqrtM, rem = i % SqrtM;
			if(rem <= children[child].getMax()) {
				return child * SqrtM + children[child].findNext(rem);
			}else {
				int nextChild = summary.findNext(child + 1);
				if(nextChild == SqrtM)
					return M;
				return nextChild * SqrtM + children[nextChild].getMin();
			}
		}

		int findPrev(int i) const {
			if(i < 0) return -1;
			int child = i / SqrtM, rem = i % SqrtM;
			if(children[child].getMin() <= rem) {
				return child * SqrtM + children[child].findPrev(rem);
			}else {
				int prevChild = summary.findPrev(child - 1);
				if(prevChild == -1)
					return -1;
				return prevChild * SqrtM + children[prevChild].getMax();
			}
		}
	};

	struct VEBTree {
		static const int M = NodeLv2::M;

		NodeLv2 root;

		VEBTree() { clear(); }

		void clear() { root.clear(); }

		bool empty() const { return root.empty(); }
		int getMin() const { return empty() ?  M : root.getMin(); }
		int getMax() const { return empty() ? -1 : root.getMax(); }

		bool get(int i) const { return root.get(i); }

		void insert(int i) { root.insert(i); }
		void remove(int i) { root.remove(i); }

		int findNext(int i) const { return root.findNext(i); }
		int findPrev(int i) const { return root.findPrev(i); }
	};
}

int main() {
	using namespace vEB_tree;

	int N;
	scanf("%d", &N);
	vector<int> A(N), B(N);
	rep(i, N) {
		scanf("%d", &A[i]);
//		A[i] = rand() % 10000 + 1;
	}
	rep(i, N) {
		scanf("%d", &B[i]);
//		B[i] = rand() % 10000 + 1;
	}

	sort(all(A));
	rep(i, N) B[i] /= 2;

	const int X = *max_element(all(A)) + *max_element(all(B));
	const int Y = 1500;
	const int logY = 11, maskY = (1 << logY) - 1;

	const int VEBs = 2, VEBSize = VEBTree::M;
	assert(((X + 1) << logY) < VEBSize * VEBs);

	VEBTree *vebs[VEBs];
	rep(k, VEBs) vebs[k] = new VEBTree;

	int ans = INF;
	rep(i, N) {
		rep(j, N) {
			int p = A[j] << logY | 0;
			vebs[p / VEBSize]->insert(p % VEBSize);
		}

		int curk = 0;
		int x = 0;
		for(int j = i; ; ) {
			int p;
			while(1) {
				p = vebs[curk]->getMin();
				if(p != VEBTree::M) {
					vebs[curk]->remove(p);
					p += curk * VEBSize;
					break;
				}
				++ curk;
			}
			amax(x, (p & maskY) + 1);

			int np = p + (B[j] << logY) + 1;
			vebs[np / VEBSize]->insert(np % VEBSize);

			if((++ j) == N) j = 0;
			if(j == i) break;
		}

		for(; curk < VEBs; ++ curk) {
			while(1) {
				int p = vebs[curk]->getMin();
				if(p == VEBTree::M) break;
				vebs[curk]->remove(p);
			}
		}

		amin(ans, x);
	}
	printf("%d\n", ans);
	return 0;
}
0