Submission #577738

#	Time	Username	Problem	Language	Result	Execution time	Memory
577738		8e7	Triangles (CEOI18_tri)	C++17	100 / 100	34 ms	2132 KiB

tri

//Challenge: Accepted
#include "trilib.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);

bool query(int a, int b, int c){
	return is_clockwise(a, b, c);
}
bool cmp(int i, int j) {
	return query(1, i, j);
}
int main() {
	io
	int n = get_n();
	vector<int> up, low;
	for (int i = 3;i <= n;i++) {
		if (query(1, 2, i))	up.push_back(i);
		else low.push_back(i);
	}
	sort(up.begin(), up.end(), cmp);	
	sort(low.begin(), low.end(), cmp);
	pary(up.begin(), up.end());
	pary(low.begin(), low.end());
	deque<int> hull;	
	hull.push_back(2);
	auto add = [&] (int i) {
		while (hull.size() > 1) {
			int cur = hull.back(), prv = hull[hull.size() - 2];
			if (!query(prv, cur, i)) hull.pop_back();
			else {
				break;
			}
		}
		hull.push_back(i);
		debug(i);
		pary(hull.begin(), hull.end());
	};
	for (int i:up) add(i);	
	add(1);
	for (int i:low) add(i);
	while (hull.size() > 2) {
		if (!query(hull.back(), hull[0], hull[1])) hull.pop_front();	
		else if (!query(hull[hull.size() -2], hull.back(), hull[0])) hull.pop_back();
		else {
			break;
		}
	}
	give_answer(hull.size());
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:15:19: warning: statement has no effect [-Wunused-value]
   15 | #define pary(...) 0
      |                   ^
tri.cpp:41:2: note: in expansion of macro 'pary'
   41 |  pary(up.begin(), up.end());
      |  ^~~~
tri.cpp:15:19: warning: statement has no effect [-Wunused-value]
   15 | #define pary(...) 0
      |                   ^
tri.cpp:42:2: note: in expansion of macro 'pary'
   42 |  pary(low.begin(), low.end());
      |  ^~~~
tri.cpp: In lambda function:
tri.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
tri.cpp:54:3: note: in expansion of macro 'debug'
   54 |   debug(i);
      |   ^~~~~
tri.cpp:15:19: warning: statement has no effect [-Wunused-value]
   15 | #define pary(...) 0
      |                   ^
tri.cpp:55:3: note: in expansion of macro 'pary'
   55 |   pary(hull.begin(), hull.end());
      |   ^~~~

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