Submission #1039266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039266		Trustfulcomic	Triangles (CEOI18_tri)	C++14	55 / 100	1889 ms	1340 KiB

tri

#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;

int main(){
    int n = get_n();
    if (n <= 3){
        give_answer(n);
    } else {
        vector<int> hull = {0,1,2};
        for (int i = 3; i<n; i++){
            vector<int> doteky;
            for (int j = 0; j<hull.size(); j++){
                if (is_clockwise(i+1,hull[(j+1)%hull.size()]+1,hull[j]+1) == is_clockwise(i+1,hull[(j+1)%hull.size()]+1,hull[(j+2)%hull.size()]+1)){
                    doteky.push_back((j+1)%hull.size());
                }
            }
            if (doteky.size() < 2) continue;

            int m_i = min(doteky[0],doteky[1]);
            int v_i = max(doteky[0],doteky[1]);
            int m = hull[m_i];
            int v = hull[v_i];

            vector<int> f_part;
            vector<int> s_part;
            
            bool is_f = true;
            for (int i = 1; i<hull.size(); i++){
                if (m_i+i == v_i) {
                    is_f = false;
                    continue;
                }

                if (is_f){
                    f_part.push_back(hull[(m_i+i)%hull.size()]);
                } else {
                    s_part.push_back(hull[(m_i+i)%hull.size()]);
                }
            }

            vector<int> new_hull;
            if (f_part.size() != 0){
                if (is_clockwise(m+1,v+1,i+1) == is_clockwise(m+1,v+1,f_part[0]+1)){
                    new_hull.push_back(i);
                    new_hull.push_back(v);
                    for(int i : s_part){
                        new_hull.push_back(i);
                    }
                    new_hull.push_back(m);
                } else {
                    new_hull.push_back(i);
                    new_hull.push_back(m);
                    for(int i : f_part){
                        new_hull.push_back(i);
                    }
                    new_hull.push_back(v);
                }
            } else {
                if (is_clockwise(m+1,v+1,i+1) != is_clockwise(m+1,v+1,s_part[0]+1)){
                    new_hull.push_back(i);
                    new_hull.push_back(v);
                    for(int i : s_part){
                        new_hull.push_back(i);
                    }
                    new_hull.push_back(m);
                } else {
                    new_hull.push_back(i);
                    new_hull.push_back(m);
                    for(int i : f_part){
                        new_hull.push_back(i);
                    }
                    new_hull.push_back(v);
                }
            }
            hull = new_hull;
        }
        give_answer(hull.size());
    }
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:13:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |             for (int j = 0; j<hull.size(); j++){
      |                             ~^~~~~~~~~~~~
tri.cpp:29:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             for (int i = 1; i<hull.size(); i++){
      |                             ~^~~~~~~~~~~~

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