Submission #3723226


Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
template<class T, class BiOp >
struct SegmentTree {
	vector<T> data;
	T e;
	BiOp op;
	int size;
	SegmentTree(int n, T e, BiOp op) :e(e), op(op) {
		size = 1;
		while (size < n) size *= 2;
		data.resize(size * 2 - 1);
		for (int i = 0; i < size * 2 - 1; i++) data[i] = e;
	}
	void update(int k, T v) {
		k += size - 1;
		data[k] = v;
		while (k > 0) {
			k = (k - 1) / 2;
			data[k] = op(data[k * 2 + 1], data[k * 2 + 2]);
		}
	}
	T query(int a, int b, int k, int l, int r) const {
		if (b <= l || r <= a) return e;
		if (a <= l && r <= b) {
			return data[k];
		}
		return op(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
	}
	T query(int a, int b) const {
		return query(a, b, 0, 0, size);
	}
	T get(int i) {
		return data[i + size - 1];
	}
};
struct BiOp {
	int operator()(int a, int b) const {
		return min(a, b);
	}
};
int C[100000], A[100000];
int grundy[100000];
int main() {
	int N;
	cin >> N;
	for (int i = 1; i < N; i++) {
		cin >> C[i] >> A[i];
		A[i] %= 2;
	}
	SegmentTree<int, BiOp> S(N, 1 << 30, BiOp());
	S.update(0, 0);
	for (int i = 1; i < N; i++) S.update(i, -1);
	for (int i = 1; i < N; i++) {
		int tmp = S.get(0);
		if (tmp == -1 || i - tmp > C[i]) {
			S.update(0, i);
			continue;
		}
		int l = 0, r = N;
		while (r - l > 1) {
			int m = (l + r) / 2;
			int k = S.query(0, m + 1);
			if (k == -1 || i - k > C[i]) {
				r = m;
			}
			else {
				l = m;
			}
		}
		grundy[i] = l + 1;
		S.update(l + 1, i);
	}
	int g = 0;
	for (int i = 1; i < N; i++) {
		if (A[i]) g ^= grundy[i];
	}
	if (g) cout << "First" << endl;
	else cout << "Second" << endl;
}

Submission Info

Submission Time
Task C - 茶碗と豆
User Div9851
Language C++14 (GCC 5.4.1)
Score 104
Code Size 1844 Byte
Status AC
Exec Time 182 ms
Memory 2432 KB

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3
Score / Max Score 0 / 0 80 / 80 20 / 20 4 / 4
Status
AC × 3
AC × 13
AC × 21
AC × 29
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
Dataset1 sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt
Dataset2 sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt
Dataset3 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 1 ms 256 KB
01-04.txt AC 1 ms 256 KB
01-05.txt AC 1 ms 256 KB
01-06.txt AC 1 ms 256 KB
01-07.txt AC 1 ms 256 KB
01-08.txt AC 1 ms 256 KB
01-09.txt AC 1 ms 256 KB
01-10.txt AC 1 ms 256 KB
02-01.txt AC 1 ms 256 KB
02-02.txt AC 1 ms 256 KB
02-03.txt AC 1 ms 256 KB
02-04.txt AC 1 ms 256 KB
02-05.txt AC 1 ms 256 KB
02-06.txt AC 1 ms 256 KB
02-07.txt AC 1 ms 256 KB
02-08.txt AC 1 ms 256 KB
03-01.txt AC 178 ms 2432 KB
03-02.txt AC 182 ms 2432 KB
03-03.txt AC 181 ms 2432 KB
03-04.txt AC 182 ms 2432 KB
03-05.txt AC 181 ms 2432 KB
03-06.txt AC 180 ms 2432 KB
03-07.txt AC 90 ms 2432 KB
03-08.txt AC 90 ms 2432 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB