Submission #585063

#	Time	Username	Problem	Language	Result	Execution time	Memory
585063		hibiki	Triangles (CEOI18_tri)	C++11	20 / 100	3020 ms	300 KiB

tri

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

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

int n, cnt = 0, st, lst;
vector<int> v;

int main()
{
    n = get_n();
    v.pb(1);
    v.pb(2);
    for(int i = 3; i <= n; i++)
    {
        while(sz(v) > 1 && is_clockwise(v[sz(v) - 2], v[sz(v) - 1], i))
            v.pop_back();
        v.pb(i);
    }
    cnt = 1;
    st = lst = v[1];
    while(1)
    {
        for(int i = 1; i <= n; i++)
        {
            if(i == lst) continue;
            bool ok = true;
            for(int j = 1; j <= n; j++)
            {
                if(j == i || j == lst) continue;
                if(!is_clockwise(lst, i, j))
                {
                    ok = false;
                    break;
                }
            }
            if(ok)
            {
                // printf("%d %d\n",lst,i);
                if(i == st)
                {
                    give_answer(cnt);
                    return 0;
                }
                cnt++;
                lst = i;
                break;
            }
        }
    }
    return 0;
}

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