Submission #94348

#	Time	Username	Problem	Language	Result	Execution time	Memory
94348		Noam527	Triangles (CEOI18_tri)	C++17	100 / 100	27 ms	2804 KiB

tri

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;

void debug(string names) {
	cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
	int pos = 0;
	for (; pos < names.size() && names[pos] != ' ' && names[pos] != ','; pos++)
		cout << names[pos];
	cout << ": " << par << "  ";
	while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
		pos++;
	}
	names.erase(names.begin(), names.begin() + pos);
	debug(names, left...);
}

struct fenwick {
	int n;
	vector<int> tree;
	fenwick() {}
	fenwick(int sz) {
		n = sz + 1;
		tree.resize(n, 0);
	}
	void upd(int pos) {
		for (pos++; pos <= n; pos += (pos & -pos)) tree[pos]++;
	}
	int query(int pos) {
		int rtn = 0;
		for (pos++; pos; pos -= (pos & -pos)) rtn += tree[pos];
		return rtn;
	}
	int query(int l, int r) {
		return query(r) - query(l - 1);
	}
};

#include "trilib.h"
/*
int get_n() {
	cout << "n? ";
	int n;
	cin >> n;
	return n;
}
bool is_clockwise(int a, int b, int c) {
	cout << "clock " << a << " " << b << " " << c << " ";
	bool rtn;
	cin >> rtn;
	return rtn;
}
void give_answer(int s) {
	cout << "answer: " << s << '\n';
}
*/
bool clock(int a, int b, int c) {
	return is_clockwise(1 + a, 1 + b, 1 + c);
}

int n;

bool cmp(int a, int b) {
	return clock(0, a, b);
}

void merge(vector<int> &a, int l, int r) {
	static int A[40404];
	int mid = (l + r) / 2, nl = l, nr = mid + 1, nxt = l;
	while (nl <= mid && nr <= r) {
		if (cmp(a[nl], a[nr]))
			A[nxt++] = a[nl++];
		else
			A[nxt++] = a[nr++];
	}
	while (nl <= mid) A[nxt++] = a[nl++];
	while (nr <= r) A[nxt++] = a[nr++];
	for (int i = l; i <= r; i++) a[i] = A[i];
}

void msort(vector<int> &a, int l, int r) {
	if (l >= r) return;
	int mid = (l + r) / 2;
	msort(a, l, mid);
	msort(a, mid + 1, r);
	merge(a, l, r);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	n = get_n();
	vector<int> L, R;
	L.push_back(1);
	for (int i = 2; i < n; i++)
		if (clock(0, 1, i))
			R.push_back(i);
		else
			L.push_back(i);
	msort(L, 0, (int)L.size() - 1);
	msort(R, 0, (int)R.size() - 1);
	L.insert(L.begin(), 0);
	vector<int> c;
	for (auto &i : L) {
		while (c.size() >= 2 && !clock(c[c.size() - 2], c.back(), i)) c.pop_back();
		c.push_back(i);
	}
	for (auto &i : R) {
		while (c.size() >= 2 && !clock(c[c.size() - 2], c.back(), i)) c.pop_back();
		c.push_back(i);
	}
	int val = c.size();
	for (auto &i : L) {
		while (c.size() >= 2 && !clock(c[c.size() - 2], c.back(), i)) c.pop_back();
		c.push_back(i);
	}
	for (auto &i : R) {
		while (c.size() >= 2 && !clock(c[c.size() - 2], c.back(), i)) c.pop_back();
		c.push_back(i);
	}
	give_answer((int)c.size() - val);
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25