Submission #1161269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161269		12345678	Triangles (CEOI18_tri)	C++20	55 / 100	594 ms	776 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"

using namespace std;

int n, cnt, qrs, lsz, rsz;
vector<int> l, r;
deque<int> dl, dr;

int main()
{
    n=get_n();
    for (int i=3; i<=n; i++)
    {
        if (is_clockwise(1, 2, i)) r.push_back(i);
        else l.push_back(i);
    }
    lsz=l.size();
    rsz=r.size();
    for (int i=0; i<lsz; i++) for (int j=0; j<lsz-1; j++) if (!is_clockwise(1, l[j], l[j+1])) swap(l[j], l[j+1]);
    for (int i=0; i<rsz; i++) for (int j=0; j<rsz-1; j++) if (!is_clockwise(2, r[j], r[j+1])) swap(r[j], r[j+1]);
    dl.push_back(1);
    for (int i=0; i<lsz; i++)
    {
        while (dl.size()>=2&&!is_clockwise(dl[dl.size()-2], dl.back(), l[i])) dl.pop_back();
        dl.push_back(l[i]);
    }
    dr.push_back(2);
    for (int i=0; i<rsz; i++)
    {
        while (dr.size()>=2&&!is_clockwise(dr[dr.size()-2], dr.back(), r[i])) dr.pop_back();
        dr.push_back(r[i]);
    }
    while (1)
    {
        if (dl.size()>=2&&dr.size()>=1&&!is_clockwise(dr.back(), dl[0], dl[1]))
        {
            dl.pop_front();
            continue;
        }
        if (dl.size()>=1&&dr.size()>=2&&!is_clockwise(dr[dr.size()-2], dr.back(), dl[0]))
        {
            dr.pop_back();
            continue;
        }
        if (dl.size()>=2&&dr.size()>=1&&!is_clockwise(dl[dl.size()-2], dl.back(), dr[0]))
        {
            dl.pop_back();
            continue;
        }
        if (dl.size()>=1&&dr.size()>=2&&!is_clockwise(dl.back(), dr[0], dr[1]))
        {
            dr.pop_front();
            continue;
        }
        break;
    }
    give_answer(dl.size()+dr.size());
    return 0;
}

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