Submission #585128

#	Time	Username	Problem	Language	Result	Execution time	Memory
585128		hibiki	Triangles (CEOI18_tri)	C++11	0 / 100	1 ms	212 KiB

tri

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

#define pb push_back
#define sz(x) (int)x.size()

int n;
vector<int> l, r;

int main()
{
    n = get_n();
    for(int i = 3; i <= n; i++)
    {
        if(is_clockwise(1, 2, i))
            r.pb(i);
        else
            l.pb(i);
    }
    vector<int> stk1, stk2, all, last;
    stk1.pb(1);
    stk1.pb(2);
    if(sz(r))
    {
        r.pb(1);
        for(auto idx: r)
        {
            if(sz(stk1) > 1 && !is_clockwise(stk1[sz(stk1) - 2], stk1[sz(stk1) - 1], idx))
            stk1.pop_back();
            stk1.pb(idx);
        }
    }
    stk2.pb(2);
    stk2.pb(1);
    if(sz(l))
    {
        l.pb(2);
        for(auto idx: l)
        {
            if(sz(stk2) > 1 && !is_clockwise(stk2[sz(stk2) - 2], stk2[sz(stk2) - 1], idx))
            stk2.pop_back();
            stk2.pb(idx);
        }
    }
    all.pb(2);
    for(int i = 2; i < sz(stk1) - 1; i++)
        all.pb(stk1[i]);
    all.pb(1);
    for(int i = 2; i < sz(stk2) - 1; i++)
        all.pb(stk2[i]);
    all.pb(2);
    last.pb(all[0]);
    last.pb(all[1]);
    for(int i = 2; i < sz(all); i++)
    {
        if(sz(last) > 1 && !is_clockwise(last[sz(last) - 2], last[sz(last) - 1], all[i]))
            last.pop_back();
        last.pb(all[i]);
    }
    give_answer(sz(last) - 1);
    return 0;
}

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