Submission #267127

#	Time	Username	Problem	Language	Result	Execution time	Memory
267127		ly20	Triangles (CEOI18_tri)	C++17	55 / 100	1834 ms	1528 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;
set <pair <int, int> > s;
const int MAXN = 41234;
int v[MAXN];
int main() {
	int n = get_n();
	if(is_clockwise(1, 2, 3)) {
		s.insert(make_pair(1, 2)); s.insert(make_pair(2, 3)); s.insert(make_pair(3, 1));
	}
	else {
		s.insert(make_pair(2, 1)); s.insert(make_pair(3, 2)); s.insert(make_pair(1, 3));
	}
	for(int i = 4; i <= n; i++) {
		set <pair <int, int> > :: iterator it;
		vector <pair <int, int> > at;
		for(it = s.begin(); it != s.end(); it++) {
			int a = it -> first, b = it -> second;
			if(!is_clockwise(a, b, i)) {
				v[a]++; v[b]++;
				at.push_back(make_pair(a, b));
			}				
		}
		int a = 0, b = 0;
		if(at.size() == 0) continue;
		for(int j = 0; j < at.size(); j++) {
			if(v[at[j].first] == 1) {
				a = at[j].first;
			}
			if(v[at[j].second] == 1) {
				b = at[j].second;
			}
			s.erase(at[j]);
		}
		for(int j = 0; j < at.size(); j++) {
			v[at[j].first]--; v[at[j].second]--;
		}
		s.insert(make_pair(a, i)); s.insert(make_pair(i, b));
		at.clear();
	}
	give_answer(s.size());
	return 0;
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(int j = 0; j < at.size(); j++) {
      |                  ~~^~~~~~~~~~~
tri.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int j = 0; j < at.size(); j++) {
      |                  ~~^~~~~~~~~~~

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