Submission #1656638


Source Code Expand

Copy

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>

auto& in = std::cin;
auto& out = std::cout;

int32_t A;
int32_t B;
int32_t C,D;

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> A>>B>>C>>D;
	out << A * 1728 + B * 144 + C * 12 + D<<endl;

	return 0;
}
#endif

#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>

auto& in = std::cin;
auto& out = std::cout;

char N[999];

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;
	if (N[0] == N[1] && N[1] != N[2] && N[2] == N[3]) {
		out << "Yes\n";
	}
	else {
		out << "No\n";
	}

	return 0;
}
#endif


#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>

auto& in = std::cin;
auto& out = std::cout;

int32_t N;
int32_t A[40000];
int32_t B[40000];
int32_t C[40000];

std::pair<double, int32_t> zero_V[40000];
std::pair<double, int32_t> tmp_V[40000];
int32_t zero_V_pos[40000];//i番目のzero_Vのindex

void func_xtoy(double X, std::pair<double, int32_t>(& res)[40000])
{
	for (size_t i = 0; i < N; i++)
	{
		res[i].first = double(C[i] - A[i] * X) / B[i];
		res[i].second = -zero_V_pos[i];
	}
	std::sort(res, res + N);
}
void func_ytox(double Y, std::pair<double, int32_t>(&res)[40000])
{
	for (size_t i = 0; i < N; i++)
	{
		res[i].first = double(C[i] - B[i] * Y) / A[i];
		res[i].second = -zero_V_pos[i];
	}
	std::sort(res, res + N);
}

template<typename FUNC>
//区間[b,e) でf(r)==trueとなる最大のrを探す
//predの条件:(f(i) == true && f(j) == false) ==> (i < j)
//      f(b) == true && f(e) == false
double binary_search_D(double b, double e, FUNC&& f)
{
	for (size_t i = 0; i < 70; ++i)
	{
		auto mid = (b + e) / 2;
		if (f(mid)) {
			b = mid;
		}
		else {
			e = mid;
		}
	}
	return b;
}

inline constexpr uint32_t get_min2pow(uint32_t value, uint32_t work = 1) {
	return ((value <= work) ? (work) : (get_min2pow(value, work * 2)));
}


namespace BIT
{
	// [1, n]
	std::array<int, 40000*2 + 1> bit;
	int32_t n;//nは2の累乗
	int sum(int i) {
		int s = 0;
		while (i > 0) {
			s += bit[i];
			i -= i & -i;
		}
		return s;
	}
	void add(int i, int x) {
		while (i <= n) {
			bit[i] += x;
			i += i & -i;
		}
	}
	void init() {
		n = 1;
		while (n < N) { n *= 2; }
		for (int32_t i = 0; i <= n; i++)
		{
			bit[i] = 0;
		}
	}
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;
	for (int32_t i = 0; i < N; i++)
	{
		in >> A[i] >> B[i] >> C[i];
	}

	//Xを求める!!!
	for (int32_t i = 0; i < N; i++)
	{
		zero_V_pos[i] = i;
	}
	func_xtoy(-1000000000.0, zero_V);
	for (int32_t i = 0; i < N; i++)
	{
		zero_V_pos[-zero_V[i].second] = i;
	}
	double X_RES = binary_search_D(-1000000000.0,+1000000000.0,
		[](double X) {
		func_xtoy(X, tmp_V);
		BIT::init();
		//交差回数を求める
		int32_t conf = 0;
		int32_t min_ = 0;
		BIT::add((-tmp_V[0].second)+1, 1);
		for (int32_t i = 1; i < N; i++)
		{
			conf += BIT::sum(N)- BIT::sum(-tmp_V[i].second);
			BIT::add((-tmp_V[i].second) + 1, 1);
		}
		return conf * 2 < (N*(N - 1) / 2);
	});

	//Yを求める!!!
	for (int32_t i = 0; i < N; i++)
	{
		zero_V_pos[i] = i;
	}
	func_ytox(-1000000000.0, zero_V);
	for (int32_t i = 0; i < N; i++)
	{
		zero_V_pos[-zero_V[i].second] = i;
	}
	double Y_RES = binary_search_D(-1000000000.0, +1000000000.0,
		[](double Y) {
		func_ytox(Y, tmp_V);
		BIT::init();
		//交差回数を求める
		int32_t conf = 0;
		int32_t min_ = 0;
		BIT::add((-tmp_V[0].second) + 1, 1);
		for (int32_t i = 1; i < N; i++)
		{
			conf += BIT::sum(N) - BIT::sum(-tmp_V[i].second);
			BIT::add((-tmp_V[i].second) + 1, 1);
		}
		return conf * 2 < (N*(N - 1) / 2);
	});

	out
		<< std::fixed << std::setprecision(19)
		<< X_RES << ' ' << Y_RES << endl;

	return 0;
}
#endif

Submission Info

Submission Time
Task B - 鉛筆
User eiya
Language C++14 (Clang 3.8.0)
Score 200
Code Size 5163 Byte
Status
Exec Time 1 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 200 / 200 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
01.txt 1 ms 256 KB
02.txt 1 ms 256 KB
03.txt 1 ms 256 KB
04.txt 1 ms 256 KB
05.txt 1 ms 256 KB
06.txt 1 ms 256 KB
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB